“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 496
School of Mathematics
  Title:   Some concepts in list coloring
1.  H. Hajiabolhassan
2.  M. Ghebleh
3.  Ch. Eslahchi
  Status:   Published
  Journal: J. Combin. Math. Combin. Comput.
  Vol.:  41
  Year:  2002
  Pages:   151-160
  Supported by:  IPM
In this paper uniquely list colorable graphs are studied. A Graph G is called to be uniquely k-list colorable if it admits a k-list assignment from which G has a unique list coloring. The minimum k for which G is not uniquely k-list colorable is called the m-number of G. We show that every triangle-free uniquely colorable graph with chromatic number k+1, is uniquely k-list colorable. A bound for the m-number of graphs is given, and using this bound it is shown that every planar graph has m-number at most 4. Also we introduce list criticality in graphs and characterize all 3-list critical graphs. It is conjectured that every χ′l-critical graph is χ′-critical and the equivalence of this conjecture to the well known list coloring conjecture is shown.

Download TeX format
back to top
scroll left or right