Affordable Access

Publisher Website

Equitable colorings of outerplanar graphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
258
Identifiers
DOI: 10.1016/s0012-365x(02)00538-1
Keywords
  • Graph Coloring
  • Equitable Coloring
  • Outerplanar Graphs

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Equitable and equitable list colorings of graphs

on Theoretical Computer Science Jan 01, 2010

Oriented colorings of 2-outerplanar graphs

on Information Processing Letters Jan 01, 2007

Oriented vertex and arc colorings of outerplanar g...

on Information Processing Letters Jan 01, 2006
More articles like this..