Counterexamples in d-regular edge-colorable graphs

Question 4.2 · arXiv:2505.05339

arXiv Question low confidence— first stated 2025-06-10

Authors: Alexander Clow, Penny Haxell, Bojan Mohar

Status solved high confidence

Question 4.2 from arXiv:2505.05339 asks whether a d-regular d-edge colourable graph witnessing a counterexample to Lovász's conjecture exists for d≥4. Abiad, Garbe, Povill, and Spiegel (arXiv:2506.21286) answer this affirmatively: they prove that there exist quartic (4-regular, 4-edge-colourable) graphs whose line hypergraphs are counterexamples to Lovász's conjecture for r=4, and they explicitly cite Question 4.2 from [CHM2025] as the question being resolved.

Cited literature (1)

proof Infinitely many counterexamples to a conjecture of Lovász (2025)

Aida Abiad, Frederik Garbe, Xavier Povill, Christoph Spiegel · arXiv preprint · arXiv:2506.21286

Proves Theorem 3: there exist quartic graphs whose line hypergraphs are counterexamples to Lovász's conjecture for r=4, directly answering Question 4.2 from arXiv:2505.05339 affirmatively; also constructs an infinite family of cubic counterexamples (generalized Petersen graphs GP(5k+11,2)) for r=3.

Reviewer notes. Question 4.2 is answered for d=4 by arXiv:2506.21286, which explicitly cites it. The follow-up paper was submitted June 26, 2025, less than three weeks after the source paper's publication date.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Does there exist a $d$-regular $d$-edge colourable graph $G$ where $d\geq 4$ such that for all edges $(u_{1},v_{1}),\dots,(u_{d-1},v_{d-1})\in E(G)$, [remainder of condition not captured in source]

Context

After finding only two counterexamples to Lovász's conjecture among line hypergraphs of cubic graphs, the authors ask whether counterexamples exist for higher regularity $d\geq 4$, generalising the $r=3$ construction.

Notes. Statement truncated in source data — the condition following the list of edges 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