{4, 5} IS NOT COVERABLE: A COUNTEREXAMPLE TO A CONJECTURE OF KAISER AND ŠKREKOVSKI.

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| ∈ 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 ℕ + 3 is coverable, where ℕ + 3 = {4, 5, 6,...}. In this paper, we disprove Kaiser and Škrekovski's conjecture by showing that there exist infinitely many graphs which are not {4, 5}-coverable. [ABSTRACT FROM AUTHOR]