Equitable colorings of outerplanar graphs

Research output: Contribution to journalArticlepeer-review

Abstract

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. In this note, we prove the conjecture of Yap and Zhang that every outerplanar graph with maximum degree at most Δ admits an equitable k-coloring for every k ≥ 1 + Δ/2. This restriction on k cannot be weakened.

Original languageEnglish (US)
Pages (from-to)X373-377
JournalDiscrete Mathematics
Volume258
Issue number1-3
DOIs
StatePublished - Dec 6 2002

Keywords

  • Equitable coloring
  • Graph coloring
  • Outerplanar graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Equitable colorings of outerplanar graphs'. Together they form a unique fingerprint.

Cite this