Article ID Journal Published Year Pages File Type
427551 Information Processing Letters 2010 4 Pages PDF
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