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
n-colouring 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
(n-1)-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
nn-2
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
(n-1)-colouring
is discovered very easily (this is actually a hit for the colouring
program), and sometimes even the
n-colouring
is not discovered. Here are a few instances that the program could
colour with
n colours but not
with
n-1.
Graph
|
Description
|
g9
|
284 vertices, 3540 edges,
8-colourable
|
g12
|
761 vertices, 33526 edges,
11-colourable
|
| g14
|
419 vertices, 7687 edges,
13-colourable
|
| g16 |
390 vertices, 5965 edges,
15-colourable
|
| g201504 |
486 vertices, 19961 edges,
19-colourable
|
| m202003a |
476 vertices, 10208 edges,
19-colourable
|
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
Kn, then the labeled
vertices in
Kn
×
D(T) induce a
properly
n-coloured graph
G(T). Every graph with a proper
n-colouring avoiding
T admits a colour-preserving
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
Kn
×
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
(t-1)-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), 914--920.
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 two-parameter 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
n-colourings obtained
generally avoid
T
(after a suitable permutation of the colours).