In 1988, Jaeger conjectured that every bridgeless cubic graph $G$ admits a Petersen coloring; that is, a map $E(G) \to E(P)$ mapping any two adjacent edges of $G$ to two adjacent edges of the Petersen graph $P$. A positive resolution of Jaeger's conjecture would have immediately resolved several other famous and long-standing problems in graph theory. In July 2026, a 68-vertex counterexample was announced on X. Shortly afterwards, Putman independently presented two non-isomorphic 112-vertex counterexamples, relying solely on computer-assisted verification. In this paper, we present two counterexamples of order $52$, currently the smallest known, and provide a purely theoretical proof. In the second part, we construct an infinite family of cyclically $4$-edge-connected cubic graphs without a Petersen coloring for every even order at least $60$. Additionally, through computational verification, we show that any counterexample must have order at least $40$. Moreover, we show that our counterexamples provide a negative answer to other related problems. Finally, we conclude the paper by discussing key open problems and highlighting avenues for future work.
In 1979, Albertson and Berman conjectured that every planar graph $G$ contains an induced forest of order at least $|V(G)|/2$. This long-standing conjecture was recently disproved by several explicit counterexamples, which naturally led to several extremal and structural questions that we answer. We combine mathematica...
Wouter Cames van Batenburg, J. Goedgebeur, Jorik Jooken· 0 citations
Tutte's flow conjectures ask when a graph has a nowhere-zero flow with small integer values. We approach these questions through spanning-tree packing and an analytic minimization argument of Alon, Buci\'c, and Davies. For every integer $q\ge2$, we prove that $q$ edge-disjoint spanning trees suffice to realize every co...
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular...
For a graph $G$, denote by $a(G)$ the number of vertices in the largest induced forest in $G$. The Albertson-Berman conjecture, which had been open since 1979, states that $a(G) \geq \frac{n}{2}$ for every simple planar graph $G$ on $n$ vertices. Although the Albertson-Berman conjecture was recently resolved in the neg...
A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G-v$ is planar. We prove that every $2$-connected apex cubic graph is three-edge-colorable. This result gives the final piece of the proof for the well-known Tutte's three-edge-coloring conjecture from 1966 \cite{tutte}. The proof, as well as the result, gen...
Yuta Inoue, K. Kawarabayashi, Rintaro Matsuo et al.· 1 citation
A graph $G$ is called $F$-irregular if all its vertices have distinct $F$-degrees, defined as the number of subgraphs of $G$ isomorphic to a given graph $F$ and containing the respective vertex. We prove the Strong Conjecture about $F$-irregular graphs (Dovzhenok, Filuta, and Chuhai, 2024), which states that for every...
T. Dovzhenok, Artem Filuta· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.