31 problems

5-cycle double cover conjecture. Every bridgeless graph has a $5$-cycle double cover.

Let $G$ be a bridgeless graph, not necessarily cubic, and let $E$ denote its edge set. A cycle cover here is a list of cycles in which every edge of $G$ lies on at least one cycle.…

Let $G$ be a directed $d$-regular graph on $n$ vertices, and regard a cycle as a directed cycle, with an individual edge allowed to count as a cycle of length two as in the source.…

Cyclic 4-edge-connectivity conjecture. Up to isomorphism, the Petersen graph is the only cyclically $4$-edge-connected cubic graph with cycle covering ratio $7/5$.

Let $G$ be a bridgeless graph, and let a $5$-cycle double cover be a collection ${\cal C}=(E_0,\ldots,E_4)$ of five cycles in which every edge belongs to exactly two cycles. Equiva…

A 5-cycle double cover ($5$-CDC) of a graph $G$ is a collection ${\cal C}=(E_0,\ldots,E_4)$ of five cycles such that every edge belongs to exactly two of them. Large even-subgraph…

Let $G$ be a bridgeless cubic graph. For $U\subseteq V(G)$, let $G_U$ be obtained by expanding each vertex of $U$ into a triangle, and let $T(G)$ be the minimum size of a set $U$ f…

A cycle cover of a graph is a collection of cycles covering every edge. The depth of an edge in a cycle cover is the number of cycles containing it, and the depth of the cover is t…

Let $G$ be a cubic graph. For $U\subseteq V(G)$, let $G_U$ be the cubic graph obtained by expanding each vertex of $U$ into a triangle. For a bridgeless cubic graph $G$, let $T(G)$…

For a bridgeless graph $G$, let $scc(G)$ denote the length of a shortest cycle cover of $G$. Shortest Cycle Cover Conjecture. If $G$ is a bridgeless graph, then … This conjecture g…

High-degree double Hall cycle conjecture. If

Kostochka et al.'s conjecture. If a bigraph $G=(X,Y)$ is snp, then there is a cycle containing all vertices of $X$.

Directed edge-disjoint cycle-cover conjecture. For every $k\in\mathbb{N}$ with $k\geq 2$, if the minimum semi-degree of $G$ is at least $n/k$, then $V(G)$ can be covered by $k-1$ e…

Cycle double cover conjecture. Every cubic graph containing no bridges has a cycle double cover, or equivalently is the face graph of a simplicial surface. More generally, every br…

Ryser's conjecture. If $n$ is odd, then $\vec{K}_n$ contains a rainbow spanning subgraph in which every vertex has in-degree and out-degree equal to one. Equivalently, $\vec{K}_n$…

Let $G[X,Y]$ be a balanced bipartite graph of order $2n$, let $S$ be a subset of $X$ with $|S|\geq 2k+2$, and let $S_{C_i}$ denote the vertices of $S$ on a cycle $C_i$. Prescribed…

Let $G$ be a bridgeless cubic graph. Write $scc(G)$ for the minimum total length of a cycle cover, and let $\chi'_{e}(G)$ denote the edge-chromatic number of $G$. Perfect-matching…

Short cycle cover conjecture. Every bridgeless graph with $m$ edges has a cycle cover of length at most $1.4m$.

The $(5,2)$-even-subgraph-cover conjecture. There exist five even subgraphs of $G$ such that every edge of $G$ belongs to exactly two of them.

$(5,2)$-cycle-cover conjecture. The graph $G$ contains five even subgraphs such that every edge of $G$ belongs to exactly two of them.

The (5, 2)-cycle-cover conjecture. The graph $G$ contains five even subgraphs such that every edge of $G$ belongs to exactly two of them.

Regular edge-connected cycle cover conjecture. There exists a cycle $(k-1)$-cover of $G$.

Goddyn's conjecture. There exists a cycle double cover of $G$ containing $C$.

Let $G$ be a bridgeless graph with $m$ edges, and let the length of a cycle cover be the sum of the lengths of all cycles in the cover. Short Cycle Cover Conjecture. Every bridgele…

Grinshpun–Sárközy powers-of-cycles conjecture. The vertex set of every $2$-colored complete graph can be covered by at most