Is there a 5-chromatic cubelike graph?

I’m in Singapore at the moment, spending the weekend watching my 11-year old daughter Amy in a gymnastics competition and the weekdays visiting Dave Roberson (currently at NUS) and Fengming Dong (currently at NTU).

Meeting up with Dave and thinking once again about the annoyingly resistant conjecture that the core of a cubelike graph is cubelike, reminded me of another “cubelike” question that is still unresolved.

First some terminology: a cubelike graph is a Cayley graph for the elementary abelian 2-group Z_2^n; the term “cubelike” arises for two reasons:

  1. The n-dimensional cube is cubelike
  2. If you talk, or write, anything about these graphs, you rapidly need something snappier for the phrase “a Cayley graph for an elementary abelian 2-group”

It has been known for decades that a cubelike graph cannot have chromatic number 3, and this was proved in a beautifully elegant fashion by Payan. A very ambitious conjecture that all cubelike graphs have chromatic number equal to a power of 2 can be disproved by exhibiting a cubelike graph on 16 vertices with chromatic number 7, and cubelike graphs on 64 vertices with chromatic number 6.

But what about 5?

I simply cannot find any cubelike graph with chromatic number 5, and according to Brouwer’s website, this is unknown. Chris Godsil and I thought about this a few years ago, and someone said they had heard someone tell someone else that they had heard that perhaps some Russians had found such a graph on 128 vertices.

So, what’s the problem? Why not just construct all 128-vertex cubelike graphs and check their chromatic number?

The trouble with this is that the number of cubelike graphs grows very rapidly. There are only 1372 such graphs on 32 vertices, and we can find all the chromatic numbers. This jumps to 475499108 on 64 vertices (actually a handful less, this overcounts the number by about 10, due to some “accidental” isomorphisms), and although I don’t know the exact chromatic number of all of these, I can rule out enough of them as potential 5-chromatic graphs to complete the search.

But on 128 vertices, we have 1038397981840994509577948 graphs to work through (that’s just about 10^{30} and so unless we stumble on one somehow (perhaps someone knows who “the Russians” are) or make some theoretical advance, this problem is likely to remain unresolved for the time being.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Up ↑

%d bloggers like this: