Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427551 | Information Processing Letters | 2010 | 4 Pages |
Abstract
We consider the coloring game and the marking game on graphs with bounded number of cycles passing through any edge. We prove that the game coloring number of a graph G is at most c+4, if every edge of G belongs to at most c different cycles. This result covers two earlier bounds on the game coloring number: for trees (c=0) and for cactuses (c=1).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics