Affordable Access

Publisher Website

Restricted list coloring and Hall's condition

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
249
Identifiers
DOI: 10.1016/s0012-365x(01)00233-3
Keywords
  • Hall'S Condition
  • List Coloring

Abstract

Abstract If L is a list assignment of colors to the vertices of a graph G of chromatic number χ( G), a certain condition on L and G, known as Hall's condition, which is obviously necessary for G to have an L-coloring, is known to be sufficient if and only if each block of G is a clique. We show that if the set of colors from which the lists are drawn has size χ( G) then there exist graphs G for which Hall's condition is sufficient for an L-coloring even though not every block of G is a clique. But if the set of colors has size greater than χ( G), then Hall's condition is again sufficient if and only if each block of G is a clique.

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