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 Δ(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) Δ(H)≤1 if g(G)≥11; (2) Δ(H)≤2 if g(G)≥7; (3) Δ(H)≤4 if either g(G)≥5 or G does not contain 4-cycles and 5-cycles; (4) Δ(H)≤6 if G does not contain 4-cycles. These results are applied to find the following upper bounds for the game coloring number colg(G) of G: (1) colg(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) colg(G)≤10 if G does not contain 4-cycles.