Some concepts in list coloring

Details Some concepts in list coloring Some concepts in list coloring

1999-06-02

arxiv.org/abs/math/9906011v2

Journal of Combinatorial Mathematics and Combinatorial Computing 41 (2002), 151-160

Mathematics

Combinatorics

Scientific paper

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 vertex 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 $\chi_\ell$-critical graph is $\chi'$-critical and the equivalence of this conjecture to the well known list coloring conjecture is shown.

Affiliated with

Also associated with

No associations

Rating

Some concepts in list coloring does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some concepts in list coloring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some concepts in list coloring will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-561189