122 problems

Let $G$ be a $2$-edge-connected cubic graph, and let $\omega(G)$ denote its oddness, the minimum number of odd circuits in a $2$-factor of $G$. Lukoťka–Máčajová–Mazák–Škoviera conj…

Nešetřil's Pentagon Conjecture. If $G$ is a cubic graph of sufficiently high girth, then $G$ is homomorphic to $C_5$.

Triangle-free cubic graph conjecture. Every triangle-free cubic graph is homomorphic to $PQ_4$.

Let $G$ be a cyclically 4-connected cubic graph, and let $F(G,t)$ denote its flow polynomial. Let $\tau=(1+\sqrt{5})/2$. Finiteness conjecture. For every $\epsilon>0$, only finitel…

Let $G$ be a bridgeless cubic graph. Mazzuoccolo's conjecture. There exist two perfect matchings $M_1,M_2$ such that the graph obtained by deleting their union,…

Let $G$ be a bridgeless cubic graph. Fan–Raspaud conjecture. The graph $G$ contains three perfect matchings $M_1,M_2,M_3$ such that no edge is covered by all three of them. The Ber…

Let $G$ be a bridgeless cubic graph. Berge–Fulkerson conjecture. The graph $G$ has six perfect matchings such that each edge of $G$ is covered by exactly two of them. This longstan…

TxGraffiti's conjecture. If $G \not\cong K_4$ and $\Delta(G)\leq 3$, then

Theo-Conjecture.

Four-perfect-matchings conjecture. The perfect matching index of $G$ is at most $4$, unless $G$ is the Petersen graph.

Strong-snark conjecture. If the perfect matching index of $G$ is greater than $4$ and $G$ is not the Petersen graph, then $G$ is a strong snark.

Let $G$ be a finite connected simple cubic graph of girth $4$, and let an ETGC denote an efficient total girth coloring. The six constructive tools considered in the source are spr…

Let $M(G)$ be a connected simple cubic map of girth $4$ embedded in a genus-realizing orientable surface, and suppose all its belts have lengths $\ell$ with $\ell\equiv 0\pmod 4$.…

Let $M(G)$ be a toroidal cubic map whose 1-skeleton is a simple cubic graph of girth $4$. Call $G$ toroidally 3-edge connected when the bicutout condition defined in the source hol…

Let $G$) be a cubic graph. The Bickle–Phillips conjecture. … If $G$ does not contain $K_4$, then … If $G$ does not contain $K_4-e$, then … The first assertion is known, while the t…

Let $G$ be a bridgeless cubic graph. An $\mathbb{S}^2$-flow is a unit vector flow with values on the unit sphere $\mathbb{S}^2$. Bobby's spherical flow conjecture. Every bridgeless…

Goddard–Henning conjecture. If

$S_{12}$-Conjecture. If $G$ is a cubic graph with a perfect matching, then

Kaiser's conjecture. For every bridgeless cubic graph $G$,

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

A cubic graph is claw-free if it has no induced subgraph isomorphic to $K_{1,3}$. A set of perfect matchings covers a graph when every edge belongs to at least one matching. Claw-f…

Abreu–Diwan–Jackson–Labbate–Schwenk's conjecture. $G$ must be $K_{3,3}$, the Heawood graph or the Pappus graph.

Abreu–Diwan–Jackson–Labbate–Schwenk's conjecture. $G$ is pseudo 2-factor isomorphic if and only if $G$ can be obtained from $K_{3,3}$, the Heawood graph or the Pappus graph by repe…