SIAM Journal on Discrete Mathematics · 2005 · 32 citations · 12 references
ComputingComputer ScienceAlgorithmsCombinatoricsComputational GeometryCombinatorial OptimizationGraph AlgorithmsGraph ColoringGraph TheoryApproximation Algorithms For ColoringColoring Planar GraphsEquitable ColoringGraph Coloring ApproximationPlanar GraphsVertex Coloring
An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. A d-degenerate graph is a graph G in which every subgraph has a vertex with degree at most d. A star Sm with m rays is an example of a 1-degenerate graph with maximum degree m that needs at least 1+m/2 colors for an equitable coloring. Our main result is that every n-vertex d-degenerate graph G with maximum degree at most n/15 can be equitably k-colored for each $k \ge 16d$. The proof of this bound is constructive. We extend the algorithm implied in the proof to an O(d)-factor approximation algorithm for equitable coloring of an arbitraryd -degenerate graph. Among the implications of this result is an O(1)-factor approximation algorithm for equitable coloring of planar graphs with fewest colors. A variation of equitable coloring (equitable partitions) is also discussed.
12
Svante Janson, Andrzej Ruciński · Random Structures and Algorithms · 2002 · 147 citations
Equitable Coloring and the Maximum Degree
Bor-Liang Chen, Ko‐Wei Lih, Pou-Lin Wu · European Journal of Combinatorics · 1994 · 134 citations
Brenda S. Baker, Edward G. Coffman · Theoretical Computer Science · 1996 · 126 citations
On equitable coloring of bipartite graphs
Ko‐Wei Lih, Pou-Lin Wu · Discrete Mathematics · 1996 · 99 citations