This is my attempt to make a random generator of graph colouring
instances based on the following theorem (an exercise in Douglas West's
textbook):
If the
chromatic number of G is n and G is properly coloured with n colours, then every tree on n vertices labeled by the colours appears
in G.
The generator (mystery, for ``miss tree'') produces a random tree
T and a graph
G with an
ncolouring avoiding
T. The output is given in DIMACS
format (see
http://dimacs.rutgers.edu/Challenges/)
with
T and the colouring
given in comments. This provides a certificate for
(n1)colourability. However the
easy recolouring algorithm uses the knowledge of which tree
T is missing. Without this
knowledge the user presumably has to scroll through all the
n^{n2}
choices, which makes the approach inefficient.
I have tested the resulting graphs only against Mike Trick's colouring
program. The result seems to be about 5% hit and 95% miss for mystery.
It is very hard to get a good instance with less than 10 colours. The
misses are of two type: sometimes the
(n1)colouring
is discovered very easily (this is actually a hit for the colouring
program), and sometimes even the
ncolouring
is not discovered. Here are a few instances that the program could
colour with
n colours but not
with
n1.
Graph

Description

g9

284 vertices, 3540 edges,
8colourable

g12

761 vertices, 33526 edges,
11colourable

g14

419 vertices, 7687 edges,
13colourable

g16 
390 vertices, 5965 edges,
15colourable

g201504 
486 vertices, 19961 edges,
19colourable

m202003a 
476 vertices, 10208 edges,
19colourable

Every tree
T with
n labels, viewed as a structure
with one binary and
n unary
relations, admits a ``dual''
D(T) which
is a maximal homomorphic image of every structure not admitting a
homomorphism from
T. In
general,
D(T)
contains loops and vertices with multiple labels.
However, if we label the vertices of the complete graph
K_{n}, then the labeled
vertices in
K_{n}
×
D(T) induce a
properly
ncoloured graph
G(T). Every graph with a proper
ncolouring avoiding
T admits a colourpreserving
homomorphism to
G(T).
The generator constructs a subgraph of
G(T).
It starts with a random Prufer code for a tree
T, and
then a random subset
S of
vertices of
D(T). It then
eliminates
dominated vertices in
K_{n}
×
S as much as
possible, and then outputs the result
G(T). One possible command
line is
mystery t s
where t is the number of vertices of
T
and
s is the number of vertices of
D(T).
The output is
(t1)colourable.
Another possible command line is
mystery t s p
where p is a parameter (generally set to 1, 2 or 3)
altering the random generation of elements of
D(T)
(as explained below).
Program

Description

mystery.c

Random graph generator

d2t.c

Converter to the colouring
program format, which randomly relabels the vertices.

colour.c

Mike Trick's colouring program

The construction used for
D(T)
is that from J. Nesetril, C.Tardif, Short answers to exponentially long
questions: extremal aspects of homomorphism duality, SIAM Journal on
Discrete Mathematics 19 (2005), 914920.
Hence the vertices of
D(T)
are functions
f
mapping each vertex of
T
to itself or to an incident edge. Two functions
f
and
g are joined
by an edge in
D(T)
if there is no edge
[i,j]
of
T such that
f(i) = [i,j] = g(j)
(loops are allowed).
The function
f
is coloured with colour
i
if
f(i) ≠ i
(
f may have many
different colours).
The generator generates random functions
f such that the probability
that
f(i) = [i,j]
is proportional to the degree of
j.
In the twoparameter version, the probability that
f(i) = i is one half.
In the three parameter version, the probability that
f(i) = i is
p/(p + ∑{d(j) : [i,j] ∈ E(T)}).
Perhaps other ways to generate
random functions would yield better results. Also, perhaps some types
of random trees are inherently better than others. My next computing
project will be to find out whether the
ncolourings obtained
generally avoid
T
(after a suitable permutation of the colours).