47 problems

Strengthened circular-flow conjecture.

A snark is a connected cubic graph with no proper 3-edge-colouring. A snark is cyclically 4-connected if no edge-cut of size at most $3$ separates two subgraphs each containing a c…

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.

Strong-snark conjecture. With the sole exception of the Petersen graph, every nontrivial snark with perfect matching index at least $5$ is strong; equivalently, all its edges are s…

Let $G$ be a cyclically $5$-edge-connected odd $2$-factored snark, where a snark is a bridgeless cubic graph of chromatic index four and odd 2-factored means that every cycle in ev…

Let $G$ be a $2$-connected cubic graph embedded in the torus. The graph $G$ is 3-edge-colorable if its edges can be colored with three colors so that adjacent edges receive differe…

Let $G$ be a cubic graph, meaning that every vertex has degree $3$, and let its girth be the length of its shortest cycle. A cubic graph is Type 2 when its total chromatic number i…

Let $G$ be a snark. Define the resistance $r(G)$ to be the minimum number of edges that can be removed from $G$ so that the resulting graph is $3$-edge-colorable, and define…

Let $G$ be a bridgeless cubic graph, let $F$ be a $2$-factor of $G$, and let $M$ be a matching in $F$. Put $H=G-M$. An $F$-matching is the matching notion defined in the paper, and…

Let $G$ be a bridgeless cubic graph. A proper $A$-coloring is a proper edge-coloring of $G$ by the non-zero elements of an abelian group $A$ such that the sum of the colors on the…

Poor-edge conjecture. If $G\not=P_{10}$, then $G$ has a normal $5$-edge-coloring with at least one poor edge. Moreover, if additionally $G\not=P_{10}^{\Delta}$, then $G$ has a norm…

Petersen Coloring Conjecture.

Let an irreducible snark be a snark for which deleting any pair of distinct vertices produces a $3$-edge-colourable graph, and let the girth of a graph be the length of its shortes…

Let $G$ be an irreducible snark, meaning a snark for which deleting any pair of distinct vertices produces a $3$-edge-colourable graph, and let defect denote colouring defect. Irre…

Let $G$ be a critical snark, let a hexagon be a $6$-cycle, and let a hexagon be double-core when it is a double-core hexagon for a $3$-array of perfect matchings. An optimal $3$-ar…

Let a critical snark be a snark in which deleting any edge yields a $3$-edge-colourable graph, and let the colouring defect of a cubic graph be the minimum number of uncovered edge…

Let $G$ be a bridgeless cubic graph, and let $\mathrm{NC}(G)$ be the set of all normal $5$-colorings of $G$. Assuming the Petersen Coloring Conjecture, define $\mathrm{poor}(G)$ as…

Let $G$ be a bridgeless cubic graph. Let $\mathrm{NC}(G)$ be the set of all normal $5$-colorings of $G$, and, assuming this set is nonempty, let $\mathrm{poor}(G)$ be the maximum n…

Let $G$ be a snark, let $\omega(G)$ denote its oddness, let $r(G)$ denote its resistance, and suppose that the buffer subgraph of $G$ is empty. Oddness–resistance conjecture with e…

Let $G$ be a bridgeless cubic graph. Write $K_G$ for its maximal conflicting subgraph, $r(G)$ for its resistance, and call $G$ a densely sparse cluster when it has the correspondin…

Let $G$ be a bridgeless cubic graph. A cycle double cover is a collection of cycles covering every edge exactly twice, and a $2$-factor is a spanning $2$-regular subgraph. Let…

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…

For every positive integer $k$, let $G_{2k+1}$ be the Goldberg snark on $8(2k+1)$ vertices, and let $\Phi_c(G_{2k+1})$ denote its circular flow number. The Goldberg snark circular-…

Let $G$ be a cubic graph. A normal edge-coloring is a proper edge-coloring in which every edge $uv$ satisfies $|S_c(u)\cup S_c(v)|\in\{3,5\}$, where $S_c(v)$ is the set of colors o…

Let $G$ be a bridgeless cubic graph, and let $\chi'_N(G)$ denote the least number of colors in a normal edge-coloring of $G$, where every edge is poor or rich. Normal 6-edge-colori…