Equitable colorings of outerplanar graphs
type: Item
instance of: scholarly article
title: Equitable colorings of outerplanar graphs
zbMATH Open document ID: 1009.05059
DOI: 10.1016/S0012-365X(02)00538-1
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1839044
zbMATH Keywords: equitable coloring
zbMATH Keywords: outerplanar graph
author: Alexandr Kostochka
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00538-1
OpenAlex ID: W2167318613
description: scientific article; zbMATH DE number 1839044