1. Equitable Coloring of Sparse Planar Graphs
- Author
-
Rong Luo, Jean-Sébastien Sereni, Gexin Yu, D. Christopher Stephens, Department of Mathematics [Morgantown], West Virginia University [Morgantown], Centre National de la Recherche Scientifique (CNRS), Department of Mathematical Sciences, Middle Tennessee State University [Murfreesboro] (MTSU), Mathematics Department [Williamsburg], and College of William and Mary [Williamsburg] (WM)
- Subjects
Vertex (graph theory) ,graphe épars ,021103 operations research ,General Mathematics ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Graph ,Planar graph ,Combinatorics ,symbols.namesake ,graphe planaire ,010201 computation theory & mathematics ,Chromatic threshold ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,FOS: Mathematics ,symbols ,Mathematics - Combinatorics ,coloration équitable ,Combinatorics (math.CO) ,Equitable coloring ,Mathematics - Abstract
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\ge m$. We show that for planar graphs $G$ with minimum degree at least two, $\chi_{eq}^*(G)\le 4$ if the girth of $G$ is at least $10$, and $\chi_{eq}^*(G)\le 3$ if the girth of $G$ is at least $14$., Comment: In the journal version, Lemma 3.1 is incorrect as stated, so in the current version we replaced its unique use (in the proof of Lemma 3.2) by a direct argument and removed Lemma 3.1. The numbering follows that of the journal version, so there is no Lemma 3.1 in this article
- Published
- 2010
- Full Text
- View/download PDF