$k$-forested coloring of planar graphs with large girth

Proceedings of the Japan Academy, Series A. Mathematical Sciences

article

Xin Zhang¹  Guizhen Liu²  Jian-Liang Wu¹ 

[1] School of Mathematics, Shandong University;Universidad Nacional de Cordoba

关键词: Acyclic coloring;    frugal coloring;    k-forested coloring;    planar graphs;    girth.;   

DOI  :  10.3792/pjaa.86.169

学科分类：数学（综合）

来源: Japan Academy

【 摘 要 】

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.

【 授权许可】

Unknown