On equitable coloring of bipartite graphs
type: Item
instance of: scholarly article
title: On equitable coloring of bipartite graphs
zbMATH Open document ID: 0856.05040
DOI: 10.1016/0012-365X(94)00092-W
author: Ko-Wei Lih
author: Pou-Lin Wu
published in: Discrete Mathematics
publication date: 1996-01-01T00:00:00Z
review text: The equitable chromatic number \(\chi_e (G)\) of a graph \(G\) is the smallest integer \(k\) such that the vertex-set of \(G\) can be partitioned into \(k\) independent sets \(V_1, \dots, V_k\) with \(|V_i |- 1 \leq |V_j |\leq |V_i |+ 1\) for any two indices \(i\) and \(j\) (i.e. there exists a proper vertex-colouring of \(G\) with exactly \(k\) colours such that all colour-classes have almost the same size). Brooks' theorem states that the usual chromatic number \(\chi (G)\) of \(G\) is at most the maximal degree \(\Delta (G)\) in \(G\) for all connected graphs \(G\) except the complete graphs and the odd cycles. The equitable colouring conjecture asserts that even \(\chi_e (G) \leq \Delta (G)\) holds for all such graphs. In the present paper, the authors verify this conjecture for all connected bipartite graphs \(G\). Moreover, they prove that \(\chi_e (G) \leq \lceil m/(n + 1) \rceil + 1\) if there exists a bipartition \((X,Y)\) of \(G\) such that \(|X |= m \geq |Y |= n\) and \(G\) has less than \(\lfloor m/(n + 1) \rfloor (m - n) + 2m\) edges.
reviewed by: Andreas Huck
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 896537
zbMATH Keywords: equitable coloring
zbMATH Keywords: equitable chromatic number
zbMATH Keywords: independent sets
zbMATH Keywords: bipartite graphs
MaRDI profile type: Publication
cites work: Q5782525
cites work: Equitable coloring of trees
cites work: Monthly Research Problems, 1969-75
cites work: Q5620621
cites work: Equitable Coloring
cites work: Q3035305
full work available at URL: 0012-365x(94)00092-w
OpenAlex ID: W2058115709
Recommended article: Q5354534
Recommended article: Q4247466
Recommended article: Q4391847
Recommended article: On certain parameters of equitable coloring of graphs
Recommended article: Q5650698
Recommended article: On equitable coloring of complete \(r\)-partite graphs
Recommended article: On equitable colorings of hypergraphs
Recommended article: Equitable coloring parameters of certain graph classes
Recommended article: Note on equitable colorings of graphs
Recommended article: Equitable coloring of hypergraphs
description: scientific article; zbMATH DE number 896537