“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 496 |
|
||||||
| Abstract: | |||||||
|
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 | |||||||
