${4,5}$ Is Not Coverable: A Counterexample to a Conjecture of Kaiser and Škrekovski
Roman Čada, Shuya Chiba, Kenta Ozeki, Petr Vrána, Kiyoshi Yoshimoto · SIAM Journal on Discrete Mathematics · 2013
For a subset $A$ of the set of positive integers, a graph $G$ is called $A$-coverable if $G$ has a cycle (a subgraph in which all vertices have even degree) which intersects all edge-cuts $T$ in $G$ with $|T| \in A$, and $A$ is said to be coverable if all graphs are $A$-coverable. As a possible approach to the dominating cycle conjecture, Kaiser and Škrekovski conjectured in [SIAM J. Discrete Math., 22 (2008), pp. 861--874] that $\mathbb{N} +3$ is coverable, where $\mathbb{N} +3 = \{4,5,6, \ldots\}$. In this paper, we disprove Kaiser and Škrekovski's conjecture by showing that there exist infinitely many graphs which are not $\{4,5\}$-coverable.