A note on relaxed equitable coloring of graphs

Hao Fan, Henry Kierstead, Guizhen Liu, Theodore Molla, Jian Liang Wu, Xin Zhang

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1062-1066
Number of pages5
JournalInformation Processing Letters
Issue number21-22
StatePublished - Dec 15 2011


  • Deficit coloring
  • Equitable coloring
  • Graph algorithms
  • Relaxed coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'A note on relaxed equitable coloring of graphs'. Together they form a unique fingerprint.

Cite this