Three-chromatic (0,2)-graphs
Status open medium confidence
The problem asks whether any finite $(0,2)$-graph (every pair of distinct vertices sharing exactly $0$ or $2$ common neighbours) can have chromatic number exactly $3$. Payan's 1992 theorem rules this out for the special subclass of cube-like graphs (Cayley graphs on $\mathbb{Z}_2^n$), but no result covering general $(0,2)$-graphs has been found in post-2007 literature.
Reviewer notes. The cube-like graphs page (aeb.win.tue.nl) confirms Payan's theorem that no cube-like graph has chromatic number 3, but cube-like graphs are a proper subclass of (0,2)-graphs. arXiv:2107.11556 (Greaves & Stanić 2021) studies spectral properties of *signed* (0,2)-graphs and does not address chromatic number. arXiv search for '(0,2)-graph' returned only two hits, neither about chromatic number 3. The ScienceDirect page for 'Homomorphisms of binary Cayley graphs' returned 403 and could not be verified. The OPG canonical page returned ECONNREFUSED. No post-2007 paper resolving or substantially advancing the chromatic number 3 question for general (0,2)-graphs was found.
Discussion
A (0,2)-graph is a graph such that every pair of distinct vertices has either 0 or 2 common neighbours. It is fairly easy to see that a (0,2)-graph is necessarily regular and a variety of other properties can be shown to hold. Although (0,2)-graphs with chromatic number 2, 4 and 5 are known it is open as to whether there can be any (0,2)-graphs with chromatic number exactly three.
Bibliography
-
★
[P]Payan, Charles: On the chromatic number of cube-like graphs, Discrete Math. 103 (1992), no. 3, 271--277.