The uniquely list chromatic number bound and equality characterization

From papers

For a graph GG and a positive integer kk, let χu(G,k)\chi_u(G,k) be the minimum number tt such that GG is uniquely (k,t)(k,t)-list colorable, and let χu(G)=maxk1χu(G,k)\chi_u(G)=\max_{k\geqslant 1}\chi_u(G,k). Let Δ(G)\Delta(G) denote the maximum degree of GG. The uniquely list chromatic number conjecture. For every graph GG,

χu(G)Δ(G)+1,\chi_u(G)\leqslant\Delta(G)+1,

and equality holds if and only if GG is either a complete graph or an odd cycle. This extends the result established in the paper for uniquely 22-list colorable graphs; the conjecture proposes the corresponding bound for all positive integers kk, together with a characterization of the equality cases.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Y. G. Ganjali, M. Ghebleh, H. Hajiabolhassan, M. Mirzazadeh and B. S. Sadjad, “Uniquely 2-List Colorable Graphs”, arXiv:math/9906187 (2008).

Solutions 0

No solutions have been posted yet.