\(k\)-forested coloring of planar graphs with large girth. (English) Zbl 1208.05022

Summary: A proper vertex coloring of a simple graph \(G\) is \(k\)-forested if the subgraph induced by the vertices of any two color classes is a forest with maximum degree at most \(k\). The \(k\)-forested chromatic number of a graph \(G\), denoted by \(\chi^{a}_{k}(G)\), is the smallest number of colors in a \(k\)-forested coloring of \(G\). In this paper, it is shown that planar graphs with large enough girth do satisfy \(\chi^{a}_{k}(G)=\lceil\frac{\Delta(G)}{k}\rceil+1\) for all \(\Delta(G)> k\geq 2\), and \(\chi^{a}_{k}(G)\leq 3\) for all \(\Delta(G)\leq k\) with the bound 3 being sharp. Furthermore, a conjecture on \(k\)-frugal chromatic number raised in [O. Amini, L. Esperet, and J. van den Heuvel, “Frugal colorings of graphs,” http://arxiv.org/pdf/0705.0422v1] has been partially confirmed.


05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] O. Amini, L. Esperet and J. van den Heuvel, Frugal Colouring of Graphs. http://arxiv.org/pdf/0705.0422v1
[2] J. A. Bondy and U. S. R. Murty, Graph theory with applications , American Elsevier Publishing Co., Inc., New York, 1976. · Zbl 1226.05083
[3] O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979), no. 3, 211-236. · Zbl 0406.05031
[4] O. V. Borodin et al., Sufficient conditions for planar graphs to be 2-distance \((\Delta+1)\)-colorable, Sib. Èlektron. Mat. Izv. 1 (2004), 129-141. · Zbl 1076.05032
[5] O. V. Borodin, A. O. Ivanova and T. K. Neustroeva, 2-distance coloring of sparse planar graphs, Sib. Èlektron. Mat. Izv. 1 (2004), 76-90. · Zbl 1077.05040
[6] O. V. Borodin, A. V. Kostochka and D. R. Woodall, Acyclic colourings of planar graphs with large girth, J. London Math. Soc. (2) 60 (1999), no. 2, 344-352. · Zbl 0940.05032
[7] T. F. Coleman and J.-Y. Cai, The cyclic coloring problem and estimation of sparse Hessian matrices, SIAM J. Algebraic Discrete Methods 7 (1986), no. 2, 221-235. · Zbl 0613.65066
[8] T. F. Coleman and J. J. Moré, Estimation of sparse Hessian matrices and graph coloring problems, Math. Programming 28 (1984), no. 3, 243-270. · Zbl 0572.65029
[9] L. Esperet, M. Montassier and A. Raspaud, Linear choosability of graphs, Discrete Math. 308 (2008), no. 17, 3938-3950. · Zbl 1203.05054
[10] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973), 390-408. · Zbl 0265.05103
[11] H. Hind, M. Molloy and B. Reed, Colouring a graph frugally, Combinatorica 17 (1997), no. 4, 469-482. · Zbl 0910.05023
[12] H. Hind, M. Molloy and B. Reed, Total coloring with \(\Delta+\text{poly}(\log\Delta)\) colors, SIAM J. Comput. 28 (1999), no. 3, 816-821. · Zbl 0917.05028
[13] A. Raspaud and W. Wang, Linear coloring of planar graphs with large girth, Discrete Math. 309 (2009), no. 18, 5678-5686. · Zbl 1191.05043
[14] R. Yuster, Linear coloring of graphs, Discrete Math. 185 (1998), no. 1-3, 293-297. · Zbl 0956.05046
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.