Three-chromatic (0,2)-graphs

Importance: Medium ✭✭
Author(s): Payan, Charles
Subject: Graph Theory
» Coloring
Recomm. for undergrads: no
Posted by: Gordon Royle
on: September 7th, 2007
Question   Are there any (0,2)-graphs with chromatic number exactly three?

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.


*[P] Payan, Charles: On the chromatic number of cube-like graphs, Discrete Math. 103 (1992), no. 3, 271--277.

* indicates original appearance(s) of problem.

Finite Three-Chromatic (0,2)-graphs

An infinite three-chromatic (0, 2)-graph is easy to construct. See Payan.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.