List Total Colouring Conjecture

Recomm. for undergrads: no
Posted by: Jon Noel
on: August 29th, 2013

\begin{conjecture} If $G$ is the total graph of a multigraph, then $\chi_\ell(G)=\chi(G)$. \end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}

The \emph{list chromatic number} of a graph $G$, denoted $\chi_\ell(G)$, is defined \Def[here]{List coloring}. Given a multigraph $H$, the \emph{total graph} $T(H)$ of $H$ is a graph on vertex set $V(T(H)):=V(H)\cup E(H)$ where \begin{itemize} \item two elements of $V(H)$ are adjacent in $T(H)$ if and only if they are adjacent in $H$; \item two elements of $E(H)$ are adjacent in $T(H)$ if and only if they share an endpoint; \item an element of $V(H)$ is adjacent to an element of $E(H)$ in $T(H)$ if it is incident with it. \end{itemize}

This problem is related to the List (Edge) Colouring Conjecture as well as the Total Colouring Conjecture.

Kostochka and Woodall [KW] conjectured that $\chi_\ell(G^2)=\chi(G^2)$ for every graph $G$; this was known as the List Square Colouring Conjecture. It is stronger than the List Total Colouring Conjecture since, given a multigraph $H$, the total graph of $H$ can be obtained by subdividing each edge of $H$ and taking the square. Moreover, the graph obtained from $H$ by subdividing each edge is bipartite and one part of the bipartition consists of vertices of degree $2$. 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].


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

*[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.