Three-chromatic (0,2)-graphs
OPG_0_2_graphs_chromatic_number_3
Status solved high confidence
Williamson proves that every finite three-colourable $(0,2)$-graph is bipartite; consequently no finite $(0,2)$-graph has chromatic number exactly three.
Cited literature (1)
-
Williamson proves that every finite three-colourable $(0,2)$-graph is bipartite; consequently no finite $(0,2)$-graph has chromatic number exactly three.
Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result.
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.