![](/files/happy5.png)
List Total Colouring Conjecture
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \chi_\ell(G)=\chi(G) $](/files/tex/0a2573f7d1a57016f919f018635cd3f9f9875fc4.png)
The list chromatic number of a graph , denoted
, is defined here. Given a multigraph
, the total graph
of
is a graph on vertex set
where
- \item two elements of
![$ V(H) $](/files/tex/dcd0d694fcb2c3f19a6ca1690b563fe1aedc5c2b.png)
![$ T(H) $](/files/tex/1a90975173493b0f8fe8843fbaec67e8ed2e9e72.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ E(H) $](/files/tex/a26b49d34b39f495639fa0588ecdb16dccd0d69f.png)
![$ T(H) $](/files/tex/1a90975173493b0f8fe8843fbaec67e8ed2e9e72.png)
![$ V(H) $](/files/tex/dcd0d694fcb2c3f19a6ca1690b563fe1aedc5c2b.png)
![$ E(H) $](/files/tex/a26b49d34b39f495639fa0588ecdb16dccd0d69f.png)
![$ T(H) $](/files/tex/1a90975173493b0f8fe8843fbaec67e8ed2e9e72.png)
This problem is related to the List (Edge) Colouring Conjecture as well as the Total Colouring Conjecture.
Kostochka and Woodall [KW] conjectured that for every graph
; this was known as the List Square Colouring Conjecture. It is stronger than the List Total Colouring Conjecture since, given a multigraph
, the total graph of
can be obtained by subdividing each edge of
and taking the square. Moreover, the graph obtained from
by subdividing each edge is bipartite and one part of the bipartition consists of vertices of degree
. Thus, the List Total Colouring Conjecture corresponds to this (very) special case of the List Square Colouring Conjecture.
However, the List Square Colouring Conjecture is not true in general. For a family of counterexamples, see the paper of Kim and Park [KP].
Bibliography
*[BKW] O. V. Borodin, A. V. Kostochka, and D. R. Woodall. List edge and list totalcolourings of multigraphs. J. Combin. Theory Ser. B, 71(2):184–204, 1997.
[KW] A. V. Kostochka and D. R. Woodall. Choosability conjectures and multicircuits. Discrete Math., 240(1-3):123–143, 2001.
[KP] Seog-Jin Kim and Boram Park: Counterexamples to the List Square Coloring Conjecture, submitted.
* indicates original appearance(s) of problem.