Disproof of a Conjecture on List Coloring

Abstract

Let \(G\) be the graph obtained from \(K_{3,3}\) by deleting an edge. We find a list assignment with \(|L(v)| = 2\) for each vertex \(v\) of \(G\), such that \(G\) is uniquely \(L\)-colorable, and show that for any list assignment \(L’\) of \(G\), if \(|Z'(v)| \geq 2\) for all \(v \in V(G)\) and there exists a vertex \(v_0\) with \(|L'(v_0)| > 2\), then \(G\) is not uniquely \(L’\)-colorable. However, \(G\) is not \(2\)-choosable. This disproves a conjecture of Akbari, Mirrokni, and Sadjad (Problem \(404\) in Discrete Math. \(266(2003) 441-451)\).