## Abstract

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 S _{m} 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 ≥ 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 arbitrary d-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.

Original language | English (US) |
---|---|

Pages (from-to) | 83-95 |

Number of pages | 13 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 19 |

Issue number | 1 |

DOIs | |

State | Published - 2005 |

## Keywords

- Equitable coloring
- Graph coloring
- d-degenerate graphs

## ASJC Scopus subject areas

- Mathematics(all)