For a survey of choosability, including relevant definitions, see [Noe] or click here.
The List Square Colouring Conjecture, due to Kostochka and Woodall [KW], states that for every graph . This was disproved by Kim and Park [KP], who proved that there is a sequence of graphs and a constant such that and for all . To obtain this lower bound from the construction of Kim and Park, one can apply the well-known result of Alon [Alo].
It may be the case that the correct upper bound for all graphs is of the same order of magnitude as the example in the result of Kim and Park.
By calculating the clique number and maximum degree of , one can easily show that (this observation is due to Young Soo Kwon), but it seems that no significantly better bound is known.
These questions are related to a problem of Zhu (see Doug West's webpage for more info) who asked whether there exists an integer such that for every graph , we have that has choice number equal to chromatic number. This conjecture has been disproved independently by Kim, Kwon and Park [KKP] and Kosar, Petrickova, Reigniger and Yeager [KPRY]. The example of [KPRY] also yields, for every , a sequence of graphs and a constant such that and for all . They ask the following, more general, questions:
To our knowledge, it is not known whether there exists a function such that the same conclusion holds. (Intuitively, it seems that higher values of should yield a smaller separation between and ; however, there seems to be no hard evidence to support this.)
These questions are also related to the so-called List Total Colouring Conjecture of Borodin, Kostochka and Woodall [BKW], which says that the total graph of a multigraph always satisfies . Given a multigraph , the total graph of can be obtained by subdividing every edge of and then taking the square of the resulting graph.
Bibliography
[Alo] Noga Alon. Choice numbers of graphs: a probabilistic approach. Combin. Probab. Comput., 1(2):107–114, 1992.
[BKW] Oleg V. Borodin, Alexandr V. Kostochka, and Douglas R. Woodall. List edge and list total colourings of multigraphs. J. Combin. Theory Ser. B, 71(2):184–204, 1997.
[KP] Seog-Jin Kim and Boram Park: Counterexamples to the List Square Coloring Conjecture, submitted.
[KKP] Seog-Jin Kim, Young Soo Kwon and Boram Park: Chromatic-choosability of the power of graphs.
[KPRY] Nicholas Kosar, Sarka Petrickova, Benjamin Reiniger, Elyse Yeager: A note on list-coloring powers of graphs.
[KW] Alexandr V. Kostochka and Douglas R. Woodall. Choosability conjectures and multicircuits, Discrete Math., 240 (2001), 123--143.
[Noe] Jonathan A. Noel. Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond, Master's thesis. McGill University (2013). pdf.
* indicates original appearance(s) of problem.