Skip to content
Preprint

Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples

Aug 2026 · 0 citations · 32 references
Mathematics

Abstract

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.

View source

Similar papers

Preprint Aug 2026

Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound

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
Preprint Oct 2026

Tree packing and the graphic Additive Base Conjecture

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

A. Jafari · 0 citations
Preprint Aug 2026

Counterexamples to two conjectures on modular edge colorings of graphs

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

Chun-Qiang Guo, Baoyindureng Wu · 0 citations
Preprint Aug 2026

A counterexample to the Albertson-Berman conjecture about induced forests in planar graphs

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

Mikhail Makarov · 1 citation
Preprint Aug 2026

Three-edge-coloring apex cubic graphs

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
Preprint Sep 2026

A Complete Proof of the Strong Conjecture about $F$-Irregular Graphs

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.