42 problems

Let $G$ be a finite undirected multigraph, allowing parallel edges and loops, and call $G$ bridgeless if it has no bridge. A cycle double cover of $G$ is a finite multiset of cycle…

Let $G$ be a bridgeless graph with $m$ edges. A cycle cover of $G$ is a collection of cycles such that every edge of $G$ belongs to at least one cycle, and $cc(G)$ denotes the mini…

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.…

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…

For positive integers $n$, $m$, and $\delta$ with $\delta\leq m$, let $G(n,m,\delta)$ be the set of all bipartite graphs with sides $X$ and $Y$ such that $|X|=n\geq 2$, $|Y|=m$, an…

The 7/5-conjecture. Every bridgeless graph has a cycle cover of length at most

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…

A finite undirected graph is bridgeless if it has no bridges, and it is cubic if every vertex has degree three. Let $P_{10}$ denote the Petersen graph. For graphs $H$ and $G$, writ…

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

Let $G$ be a graph, let $C$ be a circuit of $G$, and let $G/C$ denote the graph obtained by contracting $C$. A nowhere zero 4-flow on a graph is a 4-flow whose support contains eve…

Let $G$ be a bridgeless graph. A cycle is an Eulerian graph, and a double cycle cover is a set of cycles in which every edge is contained in precisely two cycles. Celmins–Preissman…

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 the graph under consideration. Six-cycle four-cover conjecture. The graph $G$ has six cycles such that every edge appears in exactly four of them. The supplied text give…

Let a $(k,2l)$-oriented cycle cover (abbreviated $(k,2l)$-OCC) of a graph be a family of $k$ directed cycles covering every edge exactly $2l$ times, with $l$ occurrences in each di…

Let $G$ be an $m\times n$ grid graph, and let $H$ and $K$ be two distinct disjoint cycle covers of $G$. A double-switch move is the local move defined in the source; for a general…

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…

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)$…

High-degree double Hall cycle conjecture. If

Let $G$ be a bridgeless graph, not necessarily cubic. An even subgraph is a subgraph in which every vertex has even degree. The $(5,2)$-cycle-cover conjecture. The graph $G$ contai…

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…

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…