Finite exceptions to 2-homogeneous cubic coloring

Problem 5.2 · arXiv:2511.02892

arXiv Conjecture high confidence— first stated 2025-11-04

Authors: János Barát, Zdeněk Dvořák, Penny Haxell, František Kardoš, Borut Lužar, Alfréd Onderko, Jozef Rajník, Roman Soták, Nikolay Ulyanov

Status open high confidence

The conjecture asserts that only finitely many connected bridgeless cubic graphs fail to admit a 2-homogeneous coloring. The main prior result is a 2017 paper by Janicová, Madaras, Soták, and Lužar (Ars Mathematica Contemporanea) establishing that every bipartite cubic graph admits a 2-homogeneous coloring; known exceptions are non-bipartite graphs such as the triangular prism with a subdivided edge. No paper resolving or partially resolving the full conjecture was found in a targeted search covering searches through May 2026.

Reviewer notes. No follow-up found. The conjecture was posed at the November 2025 workshop and is very recent (~6 months old). The 2017 AMC paper by Janicová, Madaras, Soták, and Lužar (https://amc-journal.eu/index.php/amc/article/view/1083) established the bipartite cubic graph case via a connection to NMNR-colorings of 3-uniform 3-regular hypergraphs; this is the closest background result but predates the conjecture.

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

Conjecture. There is a finite number of connected bridgeless cubic graphs that do not admit a $2$-homogeneous coloring.

Context

Not every cubic graph admits a 2-homogeneous coloring; for example, a graph containing a triangular prism with one edge of a triangle subdivided does not. The conjecture claims the set of exceptions is finite.

Notes. Stated as a declarative conjecture inside a labeled Problem environment.

Source paper

Open problems of the 33rd Workshop on Cycles and Colourings
János Barát, Zdeněk Dvořák, Penny Haxell, František Kardoš, Borut Lužar, Alfréd Onderko, Jozef Rajník, Roman Soták, Nikolay Ulyanov · 2025-11-04
https://arxiv.org/abs/2511.02892