zbMATH — the first resource for mathematics

Choosability conjectures and multicircuits. (English) Zbl 0989.05041
For a graph \(G\), let \(\chi(G)\), \(\chi'(G)\) and \(\chi''(G)\) respectively be the ordinary vertex, edge and total chromatic number. Let \(\text{ch}(G)\), \(\text{ch}'(G)\) and \(ch''(G)\) be the list (vertex), list (edge) and list total chromatic number of a graph \(G\). Several old and new conjectures about choosability in graphs are discussed. Some of them are the following conjectures. The list-edge-colouring conjecture (LECC): For every multigraph \(G\), \(\text{ch}'(G)=\chi'(G)\). The list-total-colouring conjecture (LTCC): For every multigraph \(G\), \(\text{ch}''(G)=\chi''(G)\). The list-square-colouring conjecture (LSCC): For every graph \(G\), \(\text{ch}(G^2)=\chi(G^2)\), where \(G^2\) is the square of \(G\). In this paper LSCC and LTCC are verified for some classes of graphs which bring the authors to new conjectures.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI