197 problems

Let $G$ be a bridgeless cubic graph, and let $P_{10}$ denote the Petersen graph. An $H$-coloring of a cubic graph $G$ is a mapping $f:E(G)\rightarrow E(H)$ such that for every vert…

Berge's conjecture. Five perfect matchings suffice to cover all the edges of $G$.

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…

A cubic bridgeless graph is a cubic graph in which no edge disconnects the graph. Lovász–Plummer conjecture. Every cubic bridgeless graph has an exponential number of perfect match…

Bondy's cubic small cycle double cover conjecture. Every simple $2$-connected cubic graph on $n$ vertices other than $K_4$ has a cycle double cover consisting of at most $n/2$ cycl…

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…

Goddard–Henning conjecture. If

Let $G$ be a cubic graph admitting a nowhere-zero $4$-flow. An edge $e$ is $4$-removable if $G-e$ has a nowhere-zero $4$-flow. Hoffmann-Ostenhof's conjecture. Every cubic graph adm…

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

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

Abreu et al.'s conjecture. $K_{3,3}$, the Heawood graph and the Pappus graph are the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graphs.

Let $G$ be a cubic graph. A two-colouring of the vertex set is a partition of $V(G)$ into two colour classes, and each class induces a subgraph of $G$. Ando's conjecture. The verti…

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…

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

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…

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…

Verstraete's conjecture. If $g\geq 6$, then

Petersen Coloring Conjecture.

Let $G$ be a cubic graph whose number of vertices is divisible by $4$. A linear forest is a forest whose components are paths. Wormald's conjecture. The edges of $G$ can be $2$-edg…

Let $G$ be a $2$-connected cubic graph of order $n$. The minimum leaf number $ml(G)$ is the minimum number of leaves among the spanning trees of $G$. Minimum leaf number conjecture…

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…

Nešetřil's universal target conjecture. For every integer $k$, there is a graph $H$ of girth at least $k$ and an integer $N$ such that every cubic graph $G$ of girth at least $N$ h…

Fractional chromatic number conjecture. The fractional chromatic number of every triangle-free cubic graph is at most

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