Equitable colorings of outerplanar graphs (Q1850075): Difference between revisions

A proper vertex coloring of a graph \(G\) is said to be equitable if the sizes of any two color classes differ by at most 1. It was conjectured by \textit{H. P. Yap} and \textit{Y. Zhang} [Bull. Inst. Math., Acad. Sin. 25, 143-149 (1997; Zbl 0882.05054)] that every outerplanar graph with maximum degree at most \(\Delta\) admits an equitable \(k\)-coloring for every \(k \geq 1 + \Delta/2\). This conjecture is proved in this paper. There are simple examples to show that the restriction on \(k\) cannot be weakened.