Three-chromatic (0,2)-graphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph, and write $N(v)=\{u\in V:uv\in E\}$ for the open neighborhood of $v$. Impose the common-neighbor condition \[ |N(u)\cap N(v)|\in\{0,2\} \qquad\text{for all distinct }u,v\in V. \] The condition applies to adjacent and nonadjacent pairs alike. It does not require that every pair have two common neighbors, nor does it require regularity or a prescribed order.

The question is whether a graph satisfying this condition can have chromatic number exactly three. Explicitly, there must exist a map $c:V\to\{1,2,3\}$ with $c(u)\ne c(v)$ on every edge, while no map with just two colors has this property. Equivalently, the graph is three-colorable and contains an odd cycle. Neither merely having a displayed three-coloring nor using all three labels in a nonminimal coloring establishes this requirement.

The existence question concerns finite graphs; an infinite example would not answer it. Connectivity can be imposed without changing existence: a three-chromatic graph has a three-chromatic connected component, and each component inherits the common-neighbor condition. A positive answer should specify or establish such a finite graph and verify both requirements. A negative answer would show that every finite graph with the displayed common-neighbor property is either bipartite or requires at least four colors.

Short English statement

Is there a finite graph requiring exactly three colors in which every pair of distinct vertices has either zero or two common neighbors?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3191 (OPG-562), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Three-chromatic (0,2)-graphs. Original problem and discussion. http://www.openproblemgarden.org/op/three_chromatic_0_2_graphs.