Equitable coloring of sparse planar graphs

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}^{\ast }(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}^{\ast }(G)\le 4$ if the girth of $G$ is at least $10$, and ${\chi }_{eq}^{\ast }(G)\le 3$ if the girth of $G$ is at least $14$.

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