×

zbMATH — the first resource for mathematics

List coloring of graphs with cycles of length divisible by a given integer. (English) Zbl 1232.05070
Brualdi, Richard A. (ed.) et al., Combinatorics and graphs. Selected papers based on the presentations at the 20th anniversary conference of IPM on combinatorics, Tehran, Iran, May 15–21, 2009. Dedicated to Reza Khosrovshahi on the occasion of his 70th birthday. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4865-4/pbk). Contemporary Mathematics 531, 117-125 (2010).
Summary: For an integer \(\ell \geq 2\), a graph \(G\) is said to be a \((0 \mod \ell)\)-cycle graph if every cycle in \(G\) has length divisible by \(\ell\). So a graph is a \((0 \mod 2)\)-cycle graph if and only if it is bipartite. We prove the following results.
(1)
In contrast with bipartite graphs, whose list chromatic number can be arbitrary large, a \((0 \mod \ell)\)-cycle graph with \(\ell \geq 3\) has the list chromatic number at most three; we give a new proof of this known result.
(2)
Extending a theorem of Galvin for bipartite graphs, we prove that the edge choosability and edge chromatic number of every \((0 \mod \,\ell)\)-cycle graph \(G\) are equal, and equal its maximum degree \(\Delta(G)\) if \(\Delta(G)\geq 3\).
(3)
We prove that the total choosability and total chromatic number of every \((0 \mod \ell)\)-cycle graph \(G\) with \(\ell \geq 3\) are equal, and equal \(\Delta(G)+ 1\) if \(\Delta(G) \geq 3\).

For the entire collection see [Zbl 1202.05003].
MSC:
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite