Equivalence of two conjectures on equitable coloring of graphs

Equivalence of two conjectures on equitable coloring of graphs

0.00 Avg rating0 Votes
Article ID: iaor20132792
Volume: 25
Issue: 4
Start Page Number: 501
End Page Number: 504
Publication Date: May 2013
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: graph coloring
Abstract:

A graph G is said to be equitably k‐colorable if there exists a proper k‐coloring of G such that the sizes of any two color classes differ by at most one. Let Δ(G) denote the maximum degree of a vertex in G. Two Brooks‐type conjectures on equitable Δ(G)‐colorability have been proposed in Chen and Yen (Discrete Math., 2011) and Kierstead and Kostochka (Combinatorica 30:201–216, 2010) independently. We prove the equivalence of these conjectures.

Reviews

Required fields are marked *. Your email address will not be published.