Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers (Q819816): Difference between revisions

Let \(G\) be a graph on the Euclidean plane, the projective plane, the torus, or the Klein bottle with girth \(g(G)\) and maximum degree \(\Delta(G)\). It is proved in this paper that \(G\) has an edge-partition into a forest and a subgraph \(H\) such that (1) \(\Delta(H) \leq 1\) if \(g(G) \geq 11\); (2) \(\Delta(H) \leq 2\) if \(g(G) \geq 7\); (3) \(\Delta(H) \leq 4\) if \(g(G) \geq 5\) or \(G\) does not contain 4-cycles and 5-cycles; (4) \(\Delta(H) \leq 6\) if \(G\) does not contain 4-cycles. Applications of these results give upper bounds for the game coloring number col\(_g(G)\) of \(G\): (1) col\(_g(G) \leq 5\) if \(g(G) \geq 11\); (2) col\(_g(G) \leq 6\) if \(g(G) \geq 7\); (3) col\(_g(G) \leq 8\) if either \(g(G) \geq 5\) or \(G\) does not contain 4-cycles and 5-cycles; (4) col\(_g(G) \leq 10\) if \(G\) does not contain 4-cycles.