Journal article
On equitable coloring of d-degenerate graphs
SIAM journal on discrete mathematics, Vol.19(1), pp.83-95
01/01/2005
DOI: 10.1137/S0895480103436505
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.
Details
- Title: Subtitle
- On equitable coloring of d-degenerate graphs
- Creators
- A V KostochkaK Nakprasit - University of Illinois Urbana-ChampaignS V Pemmaraju - University of Iowa
- Resource Type
- Journal article
- Publication Details
- SIAM journal on discrete mathematics, Vol.19(1), pp.83-95
- DOI
- 10.1137/S0895480103436505
- ISSN
- 0895-4801
- eISSN
- 1095-7146
- Publisher
- Siam Publications
- Number of pages
- 13
- Language
- English
- Date published
- 01/01/2005
- Academic Unit
- Computer Science
- Record Identifier
- 9984259436802771
Metrics
10 Record Views