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

Zhang, Xin; Liu, Guizhen; Wu, Jian-Liang

Proc. Japan Acad., Ser. A 86, No. 10, 169-173 (2010).

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.

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C15	Coloring of graphs and hypergraphs

Keywords:

acyclic coloring; frugal coloring; \(k\)-forested coloring; planar graphs; girth

References:

[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