13 problems

Let $G$ be a cyclically $5$-edge-connected odd $2$-factored snark, meaning that $G$ is a snark, every cycle in every $2$-factor of $G$ is odd, and no edge cut of size at most four…

Let $G$ be an $n$-vertex graph. A cycle-and-edge cover is a cover of the edge set of $G$ by subgraphs that are $2$-regular graphs or single edges. The linear cycle-and-edge cover c…

Let $G$ be a $6$-regular graph. A 2-factor is a spanning $2$-regular subgraph, and a component of a $2$-factor is one of its connected components. The 6-regular three-2-factor conj…

Let $k$ be a positive integer and let $G$ be a graph of order $n$. For an independent set of order $k+1$, define … when $\alpha(G)\geq k+1$, and set $\sigma_{k+1}(G)=\infty$ otherw…

Let $G$ be a claw-free graph, meaning that $G$ has no induced subgraph isomorphic to $K_{1,3}$. Let $\delta(G)$ denote its minimum degree and let $\alpha(G)$ denote its independenc…

Let $G$ be a graph of order $n$, let $k$ be a positive integer, and let $c3_{k+1}(G)$ denote the minimum degree sum over every set of $k+1$ pairwise nonadjacent vertices of $G$. De…

Let $Q_n$ be a hypercube and let a 2-factor mean a spanning 2-regular subgraph of $Q_n$. A matching is a set of pairwise vertex-disjoint edges. Vandenbussche–West conjecture. Every…

Diwan's two-edge conjecture. There exists a cycle containing both $e$ and $f$ that is contained in a 2-factor of $G$.

Faudree–Gould–Jacobson–Lesniak–Saito conjecture. For any $k\in\mathbb{N}$ there are constants $c_k<1/2$, $n_k$ and $a_k$ such that any Hamiltonian graph $G$ of order $n\ge n_k$ wit…

Erdős–Faudree conjecture. Every graph $G$ on $4n$ vertices with minimum degree at least $2n$ contains a 2-factor consisting of $\frac{n}{4}$ copies of $C_4$.

Let $G$ be an $n$-vertex $r$-regular graph with even $r\geq \frac{3}{4}n+o(n)$, and let $F$ be a $2$-regular graph on $n$ vertices. Regular spanning 2-factor decomposition conjectu…

Chvátal–Erdős conjecture. If $G$ satisfies the Chvátal–Erdős condition, then $G$ has a 2-factor with exactly $k$ cycles.

Let $K_{2n}$ be a complete graph with a proper edge-coloring using exactly $2n-1$ colors. A multicolored $2$-factor is a $2$-factor whose edges have pairwise distinct colors. The r…