On equitable \(\Delta\)-coloring of graphs with low average degree
type: Item
instance of: scholarly article
title: On equitable \(\Delta\)-coloring of graphs with low average degree
zbMATH Open document ID: 1086.05030
published in: Theoretical Computer Science
publication date: 2006-03-20T00:00:00Z
review text: An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. \textit{B.-L. Chen, K.-W. Lih}, and \textit{P.-L. Wu} [Eur. J. Comb. 15, 443--447 (1994; Zbl 0809.05050)] proposed the following conjecture. Any connected graph with maximum degree \(\Delta \geq 3\) distinct from \(K_{\Delta+1}\) and \(K_{\Delta, \Delta}\) has an equitable coloring using \(\Delta\) colors. In this paper, this conjecture is established for graphs with average degree at most \(\Delta/5\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5013296
zbMATH Keywords: equitable coloring
author: Alexandr Kostochka
author: Kittikorn Nakprasit
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.09.031
OpenAlex ID: W2152547906
cites work: Mutual exclusion scheduling
cites work: Q2735585
cites work: Equitable coloring and the maximum degree
cites work: Q4342632
cites work: Q5620621
cites work: Q4875172
cites work: The infamous upper tail
cites work: An existential problem of a weight-controlled subset and its application to school timetable construction
cites work: Equitable Colourings of d-degenerate Graphs
cites work: A list analogue of equitable coloring
cites work: Chromatic optimisation: Limitations, objectives, uses, references
cites work: Q4247466
cites work: On equitable coloring of bipartite graphs
cites work: New proof of brooks' theorem
cites work: Q4780802
cites work: Q4716273
cites work: Perfect Graphs and an Application to Optimizing Municipal Services
cites work: Q4348809
cites work: Q4255998
DOI: 10.1016/J.TCS.2005.09.031
description: scientific article; zbMATH DE number 5013296