Paperlane

no. 14 · Friday 13 November 2026

On 2-Homogeneous Colourings of Cubic Bipartite Graphs

Rong-Xia Hao, Jianbing Liu and Federico Romaniello

math.CO · 12 pp

Abstract

A proper vertex colouring is 2-homogeneous if every open neighbourhood contains exactly two colours. We show that every cubic bipartite graph admits a 2-homogeneous colouring with at most four colours, proving a conjecture of Janicová, Madaras, Soták and Lužar. For 3-connected det-extremal cubic bipartite graphs, we establish the stronger bound $χ_h^{(2)}(G) = 3$, showing that every such graph admits a fall 3-colouring.

comments
12 pages, 1 table
fields
Combinatorics
pdf ↗ page arXiv:2611.16649 ↗