Open Problem Garden - Coloring the Odd Distance Graph - Comments

The Odd-Distance Graph (re: Coloring the Odd Distance Graph)

Anonymous — Mon, 19 Mar 2012 06:03:57 +0100

In the book Research Problems in Discrete Geometry, on page 252, it is stated that every K_4 free graph is a subgraph of the odd distance graph. We just proved that W_5, the five wheel is not a subgraph of the odd distance graph. I further believe that there are triangle free graphs that are not subgraphs of the odd distance graph, and even graphs with large girth.

Flaw (re: Coloring the Odd Distance Graph)

JSteinhardt — Thu, 08 May 2008 00:44:51 +0200

Actually, it appears there is a flaw with the below proof. The spectral bound on the chromatic number assumes a measurable coloring, as we want to say the following:

but this assumes that each is Lesbegue integrable, which in turn requires measurable coloring classes.

Solution (final part) (re: Coloring the Odd Distance Graph)

JSteinhardt — Sun, 04 May 2008 01:15:56 +0200

Let be the function we are integrating. Let denote the region for which and that contains the value of where . Then we note that and the sines of the integral alternate, so we can just calculate the first one and everything else will be bounded (in particular by ). With a bit of Taylor approximation, we can bound the size of each by , and noting that is always positive for , we can replace the with and then bound by . This gives us the bound we claimed above and we are done.

Jacob Steinhardt

Solution (continued) (re: Coloring the Odd Distance Graph)

JSteinhardt — Sun, 04 May 2008 01:15:27 +0200

We see that the eigenvalue of the eigenfunction is given by

for an appropriately chosen . Thus we need only actually consider , which we from now on denote . Then some calculation gives us that the integral is

We can show that (and this will suffice) that when is near ,

Solution (re: Coloring the Odd Distance Graph)

JSteinhardt — Sun, 04 May 2008 01:14:30 +0200

I believe I have a solution. I will sketch it here. (Sorry, it's broken up into three posts because I cannot figure out how to post something more than 1000 characters...but I have seen longer solutions posted elsewhere so I assume it's okay; if not, I apologize.)

Consider the operator defined by

This is in some sense a weighting of the adjacency operator. We can then prove the result (well-known for finite graphs) that , where are the sup and inf of the spectrum of .

We note that the eigenfunctions of are simply the exponential maps .

Subgraph construction (re: Coloring the Odd Distance Graph)

Anonymous — Sat, 24 Nov 2007 05:53:32 +0100

For any rational , there is a subgraph of the odd-distance graph with

[1] Pan Zhi-Shi, Roussel Nicolas, Subgraphs of the odd-distance graph with given circular chromatic number, manuscript

NR.

Correction of previous comment (re: Coloring the Odd Distance Graph)

Anonymous — Wed, 07 Nov 2007 09:44:50 +0100

The proof is actually for .

NR.

Circular chromatic number of the odd distance graph (re: Coloring the Odd Distance Graph)

Anonymous — Wed, 31 Oct 2007 06:52:08 +0100

The proof for has been recently extended to , which implies the previous result, where is the circular chromatic number.

Nicolas Roussel.

Coloring the Odd Distance Graph

mdevos — Wed, 03 Oct 2007 05:30:29 +0200

Author(s): Rosenfeld

Subject: Graph Theory » Coloring » Vertex coloring

The Odd Distance Graph, denoted , is the graph with vertex set and two points adjacent if the distance between them is an odd integer.

Question Is ?