Abstract. We prove that for every set [Formula: see text] of vertices of a directed graph [Formula: see text], the maximum number of vertices in [Formula: see text] contained in a collection of vertex-disjoint cycles in [Formula: see text] is at least the minimum size of a set of vertices that hits all cycles containing a vertex of [Formula: see text]. As a consequence, the directed tree-width of a directed graph is linearly bounded in its cycle-width, which improves the previously known quadratic upper bound. We further show that the corresponding statement in bidirected graphs is true and that its edge-variant holds in both undirected and directed graphs, but fails in bidirected graphs. The vertex-version in undirected graphs remains an open problem.

Abstract We investigate Maker–Breaker games on graphs of size $\aleph _1$ in which Maker’s goal is to build a copy of the host graph. We establish a firm dependence of the outcome of the game on the axiomatic framework. Relating to this, we prove that there is a winning strategy for Maker in the $K_{\omega ,\omega _1}$ -game under ZFC+MA+ $\neg $ CH and a winning strategy for Breaker under ZFC+CH. We prove a similar result for the $K_{\omega _1}$ -game. Here, Maker has a winning strategy under ZF+DC+AD, while Breaker has one under ZFC+CH again.