On equitable \(\Delta\)-coloring of graphs with low average degree (Q817775)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5013296
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On equitable \(\Delta\)-coloring of graphs with low average degree |
scientific article; zbMATH DE number 5013296 |
Statements
On equitable \(\Delta\)-coloring of graphs with low average degree (English)
0 references
20 March 2006
0 references
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\).
0 references
equitable coloring
0 references
0 references
0.897756040096283
0 references
0.8951165080070496
0 references
0.8945685625076294
0 references
0.8899414539337158
0 references
