| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427774 | Information Processing Letters | 2011 | 5 Pages |
Abstract
In this note we introduce the concept of equitable d-relaxed coloring. We prove that each graph with maximum degree at most r admits an equitable 1-relaxed r-coloring and provide a polynomial-time algorithm for constructing such a coloring.
► The concept of equitable d-relaxed coloring is introduced. ► An upper bound for the equitable d-relaxed threshold is given. ► A fast algorithm for constructing an equitable 1-relaxed coloring is provided.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hao Fan, H.A. Kierstead, Guizhen Liu, Theodore Molla, Jian-Liang Wu, Xin Zhang,