List colorings and reducibility (Q1372746)

Let \(G\) be a simple graph, \(L(v)\) a list of allowed colors assigned to each vertex \(v\) of \(G\), and \(U\) an arbitrary subset of the vertex set. The graph \(G\) is called \(k\)-choosable if, for any list assignment with \(|L(v)|=k\) for all \(v\in V\), it is possible to color all vertices with colors from their lists in a proper way (i.e., no monochromatic edge occurs). We say that \(G\) is \(U\)-reducible if, for every list assignment of \(G\) where all lists have the same number of elements, we can color the vertices of \(U\) with colors from their lists such that for every vertex \(v\notin U\) at most one color of \(L(v)\) appears in the coloring of the neighbors of \(v\) which belong to \(U\). The concept of reducibility is closely related to list colorings and choosability. The main result of this paper states that a bipartite graph \(G\) is \(U\)-reducible for every maximal independent set \(U\subseteq V\) if and only if \(G\) is 2-choosable. It is also proved that if \(G\) is 2-choosable, then it is \(U\)-reducible for every \(U\subseteq V\), and that the Petersen graph, \(K_{3,4}\) and \(K_{3,5}\) are \((3m,m)\)-choosable for all \(m\geq 1\).