×

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.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI