Infinite 3-edge-colourable edge-transitive cubic graphs
Question 4.1 · arXiv:2505.05339
Status solved high confidence
Question 4.1 asks whether infinitely many 3-edge-colourable cubic graphs exist such that for every pair of edges $(u,v),(x,y)\in E(G)$ the key lemma condition holds (i.e. the line hypergraph of $G$ is a counterexample to the Lovász conjecture for $r=3$). Abiad, Garbe, Povill, and Spiegel (arXiv:2506.21286, June 2025) answer this affirmatively by constructing a simple infinite family of such counterexamples based on generalized Petersen graphs, and additionally provide specific counterexamples for $r=4$.
Cited literature (1)
-
Constructs an infinite family of 3-edge-colourable cubic graphs (generalized Petersen graphs) whose line hypergraphs are counterexamples to Lovász's conjecture for $r=3$, directly answering Question 4.1 in the affirmative; also provides counterexamples for $r=4$.
Reviewer notes. The follow-up paper (2506.21286) was submitted on 2025-06-26, just 16 days after the source paper. It explicitly credits Clow–Haxell–Mohar as the motivation and extends their single example to an infinite family, resolving Question 4.1.
Context
The authors verified computationally that the Biggs-Smith graph is the unique cubic edge-transitive graph on at most 166 vertices satisfying the key lemma's conclusion, and that F168D is the only other such graph on at most 300 vertices. This question asks whether infinitely many such graphs exist.
Notes. Statement truncated in source data — the condition following 'for all edges $(u,v),(x,y)\in E(G)$' was not captured; likely a PDF extraction issue.
Source paper
A Counterexample to a Conjecture of Lovász
Alexander Clow, Penny Haxell, Bojan Mohar · 2025-06-10
https://arxiv.org/abs/2505.05339