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.


Comments are limited to a maximum of 1000 characters.
More information about formatting options