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

TY - JOUR

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

AU - Fishburn, Peter C.

AU - Roberts, Fred S.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - Channel assignment problems

KW - Distance-two colorings

KW - No-hole colorings

UR - http://www.scopus.com/inward/record.url?scp=34249067685&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249067685&partnerID=8YFLogxK

U2 - https://doi.org/10.1137/S0895480100378562

DO - https://doi.org/10.1137/S0895480100378562

M3 - Article

SN - 0895-4801

VL - 20

SP - 428

EP - 443

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -