Equitable Coloring of Sparse Planar Graphs
Equitable Coloring of Sparse Planar Graphs
复制标题
DOI：
10.1137/090751803
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
Rong Luo;Jean-Sébastien Sereni;And D. CHRISTOPHER STEPHENS;YU Gexin
中科院分区：
文献类型：
--
作者：
Rong Luo;Jean-Sébastien Sereni;And D. CHRISTOPHER STEPHENS;YU Gexin
A proper vertex coloring of a graph $G$ is equitable if the sizes of color classes differ by at most one. The equitable chromatic threshold $\chi_{eq}^*(G)$ of $G$ is the smallest integer $m$ such that $G$ is equitably $n$-colorable for all $n\geq m$. We show that for planar graphs $G$ with minimum degree at least two, $\chi_{eq}^*(G)\leq4$ if the girth of $G$ is at least 10, and $\chi_{eq}^*(G)\leq3$ if the girth of $G$ is at least 14.
