$k$-forested coloring of planar graphs with large girth
Zhang, Xin ; Liu, Guizhen ; Wu, Jian-Liang
Proc. Japan Acad. Ser. A Math. Sci., Tome 86 (2010) no. 1, p. 169-173 / Harvested from Project Euclid
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 [1] has been partially confirmed.
Publié le : 2010-10-15
Classification:  Acyclic coloring,  frugal coloring,  $k$-forested coloring,  planar graphs,  girth,  05C10,  05C15
@article{1291644507,
     author = {Zhang, Xin and Liu, Guizhen and Wu, Jian-Liang},
     title = {$k$-forested coloring of planar graphs with large girth},
     journal = {Proc. Japan Acad. Ser. A Math. Sci.},
     volume = {86},
     number = {1},
     year = {2010},
     pages = { 169-173},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1291644507}
}
Zhang, Xin; Liu, Guizhen; Wu, Jian-Liang. $k$-forested coloring of planar graphs with large girth. Proc. Japan Acad. Ser. A Math. Sci., Tome 86 (2010) no. 1, pp.  169-173. http://gdmltest.u-ga.fr/item/1291644507/