Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers

Let G be a graph of nonnegative characteristic and let g(G) and Delta(G) be its girth and maximum degree, respectively. We show that G has an edge-partition into a forest and a subgraph H so that (1) Delta(H) <= 1 if g(G) >= 11; (2) Delta(H) <= 2 if g(G) >= 7; (3) Delta (H) <= 4 if either g(G) >= 5 or G does not contain 4-cycles and 5 -cycles; (4) Delta(H)<= 6 if G does not contain 4-cycles. These results are applied to find the following upper bounds for the game coloring number col(g) (G) of G: (1) col(g) (G) <= 5 if g (G) >= 11; (2) colg (G) <= 6 if g(G) >= 7; (3) colg(G) <= 8 if either g(G) >= 5 or G contains no 4-cycles and 5-cycles; (4) col(g)(G) <= 10 if G does not contain 4-cycles. (c) 2005 Elsevier B.V. All rights reserved.