Full color theorems for L(2, 1)-colorings

Peter C. Fishburn, Fred S. Roberts

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

The span λ(G) of a graph G is the smallest k for which G's vertices can be L(2, 1)-colored, i.e., colored with integers in {0, 1,..., k} so that adjacent vertices' colors differ by at least 2, and colors of vertices at distance two differ. G is full-colorable if some such coloring uses all colors in {0, 1,..., λ(G)} and no others. We prove that all trees except stars are full-colorable. The connected graph G with the smallest number of vertices exceeding λ(G) which is not full-colorable is C6. We describe an array of other connected graphs that are not full-colorable and go into detail on full-colorability of graphs of maximum degree four or less.

Original languageEnglish (US)
Pages (from-to)428-443
Number of pages16
JournalSIAM Journal on Discrete Mathematics
Volume20
Issue number2
DOIs
StatePublished - 2006

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Channel assignment problems
  • Distance-two colorings
  • No-hole colorings

Fingerprint

Dive into the research topics of 'Full color theorems for L(2, 1)-colorings'. Together they form a unique fingerprint.

Cite this