Graphs that are easy to colour with one too many colour

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).