4-color bound for cubic 2-homogeneous coloring
Problem 5.1 · arXiv:2511.02892
Status open high confidence
Problem 5.1 asks whether every cubic graph admitting a 2-homogeneous coloring can be 2-homogeneously colored with at most 4 colors. No paper resolving this conjecture was found in the literature. The foundational connection between NMNR-colorings of hypergraphs and homogeneous colorings of graphs (Lužar–Soták, AMC 2017) underlies the background result that bipartite cubic graphs admit 2-homogeneous colorings using at most 6 colors; the conjecture would tighten this bound to 4 for all cubic graphs that admit any 2-homogeneous coloring.
Reviewer notes. No follow-up found. This is a very recent open problem posed at the 33rd Workshop on Cycles and Colourings (2025). The relevant foundational work is Lužar and Soták, 'From NMNR-coloring of hypergraphs to homogenous coloring of graphs', Ars Mathematica Contemporanea (2017), which established the NMNR/homogeneous coloring framework and the 6-color upper bound for bipartite cubic graphs. The conjecture is open with high confidence given its recency and the absence of any follow-up in indexed literature.
Context
A $k$-homogeneous coloring is a proper vertex coloring in which exactly $k$ colors appear in the open neighborhood of every vertex. For bipartite cubic graphs it is known that at most 6 colors suffice for a 2-homogeneous coloring; the conjecture asks whether 4 always suffice whenever a 2-homogeneous coloring exists.
Notes. Stated as a declarative conjecture inside a labeled Problem environment; a weaker bipartite version appeared in prior work [2].
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