×

Edge-partitions of planar graphs and their game coloring numbers. (English) Zbl 1016.05033

Summary: Let \(G\) be a planar graph 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 (i) \(\Delta(H)\leq 4\) if \(g(G)\geq 5\); (ii) \(\Delta(H)\leq 2\) if \(g(G)\geq 7\); (iii) \(\Delta(H)\leq 1\) if \(g(G)\geq 11\); (iv) \(\Delta(H)\leq 7\) if \(G\) does not contain 4-cycles (though it may contain 3-cycles). These results are applied to find the following upper bounds for the game coloring number \(\text{col}_g(G)\) of a planar graph \(G\); (i) \(\text{col}_g(G)\leq 8\) if \(g(G)\geq 5\); (ii) \(\text{col}_g(G)\leq 6\) if \(g(G)\geq 7\); (iii) \(\text{col}_g(G)\leq 5\) if \(g(G)\geq 11\); (iv) \(\text{col}_g(G)\leq 11\) if \(G\) does not contain 4-cycles (though it may contain 3-cycles).

MSC:

05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bodlaender, Interat J Found Comput Sci 2 pp 133– (1991)
[2] Borodin, J reine angew Math 394 pp 180– (1989)
[3] Borodin, Math Notes Acad Sci USSR 48 pp 1186– (1990)
[4] Borodin, J Graph Theory 23 pp 233– (1996)
[5] Chartrand, J Combin Theory Ser B 10 pp 12– (1971)
[6] Dinski, Discrete Math 196 pp 109– (1999)
[7] Faigle, Ars Combin 35 pp 143– (1993)
[8] Guan, J Graph Theory 30 pp 67– (1999)
[9] Kampen, Discrete Math 14 pp 337– (1976)
[10] Kedlaya, J Combin Theory Ser B 67 pp 238– (1996)
[11] Kierstead, J Graph Theory 18 pp 569– (1994)
[12] Kierstead, J Combin Theory Ser B 78 pp 57– (2000)
[13] Kotzig, Mat ?as 13 pp 20– (1963)
[14] St, J London Math Soc 36 pp 445– (1961)
[15] Ringel, J Graph Theory 17 pp 755– (1993)
[16] Wu, J Graph Theory 31 pp 129– (1999)
[17] Zhu, J Combin Theory Ser B 75 pp 245– (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.