Free choosability of the cycle

arXiv1403.2339MaRDI QIDQ6249682FDOQ6249682

Yves Aubry, Olivier Togni, Jean-Christophe Godin

Publication date: 10 March 2014

Abstract: A graph $G$ is free $(a,b)$-choosable if for any vertex $v$ with $b$ colors assigned and for any list of colors of size $a$ associated with each vertex $uev$, the coloring can be completed by choosing for $u$ a subset of $b$ colors such that adjacent vertices are colored with disjoint color sets. In this note, a necessary and sufficient condition for a cycle to be free $(a,b)$-choosable is given. As a corollary, some choosability results are derived for graphs in which cycles are connected by a tree structure.

This page was built for publication: Free choosability of the cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6249682)