Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers (Q819816): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:19, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers |
scientific article |
Statements
Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers (English)
0 references
29 March 2006
0 references
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.
0 references
Euler characteristic
0 references