Home » Subject » Graph Theory » Coloring » Vertex coloring

Circular colouring the orthogonality graph

Importance: Medium ✭✭
Author(s): DeVos, Matt
Ghebleh, Mohammad
Goddyn, Luis A.
Mohar, Bojan
Naserasr, Reza
Subject: Graph Theory
» Coloring
» » Vertex coloring
Keywords: circular coloring
geometric graph
orthogonality
Recomm. for undergrads: no
Posted by: mdevos
on: September 23rd, 2008

Let $ {\mathcal O} $ denote the graph with vertex set consisting of all lines through the origin in $ {\mathbb R}^3 $ and two vertices adjacent in $ {\mathcal O} $ if they are perpendicular.

Problem   Is $ \chi_c({\mathcal O}) = 4 $?

In the problem statement, $ \chi_c $ denotes the circular chromatic number.

Coloring properties of $ {\mathcal O} $ are, rather surprisingly, of interest in quantum mechanics. If the spins of certain particles are measured in three orthogonal directions, then these measurements always return one $ 0 $ and two values which are $ \pm 1 $. If such a particle has "decided" in advance how it will respond to any possible measurement, then the set of directions in which it will respond $ 0 $ must be an independent set in the orthogonality graph $ {\mathcal O} $ which meets every triangle. Kochen and Specker have shown that $ {\mathcal O} $ (even certain finite subgraphs of it) does not have any independent set meeting every triangle, thus exhibiting a rather mysterious property of these particles. In some sense, if the person doing the measurement has the free will to decide in which directions to measure, then the particle must have some free will to decide how it will respond.

The property that $ {\mathcal O} $ has no independent set which meets every triangle shows that $ \chi({\mathcal O}) \ge 4 $. On the other hand, if we center a regular octahedron at the origin, and assign a color to each line $ L $ depending on which pair of opposite faces it passes through (if $ L $ meets more than one pair of opposite faces, just choose one) we get a proper 4-coloring of $ {\mathcal O} $. Therefore, $ \chi({\mathcal O}) = 4 $.

These bounds prove that $ 3 \le \chi_c({\mathcal O}) \le 4 $. By investigating certain finite subgraphs of $ {\mathcal O} $, DeVos, Ghebleh, Goddyn, Mohar, and Naserasr have shown that $ \chi_c({\mathcal O}) \ge 3.5 $.

Related problems

Partitioning the Projective Plane
The Double Cap Conjecture

Bibliography



* indicates original appearance(s) of problem.
add new comment

Still open?

On September 28th, 2009 Anonymous says:

Does anyone know if this problem is still open?

reply

pretty sure

On September 28th, 2009 md says:

I am pretty confident this is still open. Apart from this one many-author paper, I don't think it has received any significant attention.

reply

This is problem 10769 of the

On November 4th, 2008 Anonymous says:

This is problem 10769 of the American Mathematical Monthly. The solution appeared in AMM 108 (2001), 774-775. See also http://tph.tuwien.ac.at/~svozil/publ/blatter.htm

Christian Blatter

reply

not exactly!

On November 4th, 2008 mdevos says:

The problem you mention, 10769 of the AMM, concerns the chromatic number of the orthogonality graph. The problem here concerns the circular chromatic number of the orthogonality graph, and I believe it is still open.

reply

Comment viewing options

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