122 problems

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

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…

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. 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. A collection of perfect matchings is an edge-covering collection when every edge of $G$ belongs to at least one matching in the collection. Ber…

Goddard–Henning conjecture. If

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. A perfect matching is a set of edges meeting every vertex exactly once, and an edge-cut is the set of edges joining a vertex subset to its comp…

Petersen Coloring Conjecture.

Let $G$ be a connected cubic graph. Hoffmann-Ostenhof's 3-Decomposition Conjecture. $G$ can be decomposed into a spanning tree, a collection of cycles, and a possibly empty matchin…

Let $G$ be a bridgeless cubic graph. A Fulkerson cover is a list of six perfect matchings of $G$ in which every edge is contained in exactly two matchings. Fulkerson's conjecture.…

A crumby coloring of a graph is a red-blue vertex coloring in which the blue subgraph has maximum degree at most $1$ and the red subgraph has minimum degree at least $1$ and contai…

Let $G$ be a connected cubic graph, and let $V(G)$ denote its vertex set. A dominating set is a subset of vertices such that every vertex outside the subset has a neighbor in it. R…

Let $G$ be a bridgeless cubic graph, and let a bipartite core mean a core whose underlying graph is bipartite. Bipartite core conjecture. Every bridgeless cubic graph has a biparti…

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…

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…