Find the Chromatic Number

Question

Surprisingly, we haven't had any challenges on graph colouring yet!

Given an undirected graph, we can give each vertex a colour such that no two adjacent vertices share the same colour. The smallest number χ of distinct colours necessary to achieve this is called the chromatic number of the graph.

For example, the following shows a valid colouring using the minimum number of colours:

_{(Found on Wikipedia)}

So this graph's chromatic number is χ = 3.

Write a program or function which, given a number of vertices N < 16 (which are numbered from 1 to N) and a list of edges, determines a graph's chromatic number.

You may receive the input and produce the output in any convenient format, as long as the input is not pre-processed. That is, you can use a string or an array, add convenient delimiters to the string or use a nested array, but whatever you do, the flattened structure should contain the same numbers as the examples below (in the same order).

You may not use built-in graph-theory related functions (like Mathematica's ChromaticNumber).

You may assume that the graph has no loop (an edge connecting a vertex with itself) as that would make the graph uncolourable.

This is code golf, the shortest answer (in bytes) wins.

Examples

Your program must at least solve all of these in a reasonable amount of time. (It must solve all inputs correctly, but it may take longer for larger inputs.)

To shorten the post, in the following examples, I present the edges in a single comma-separated list. You may instead use line breaks or expect the input in some convenient array format, if you prefer.

Triangle (χ = 3)

3
1 2, 2 3, 1 3

"Ring" of 6 vertices (χ = 2)

6
1 2, 2 3, 3 4, 4 5, 5 6, 6 1

"Ring" of 5 vertices (χ = 3)

5
1 2, 2 3, 3 4, 4 5, 5 1

Example picture above (χ = 3)

6
1 2, 2 3, 3 4, 4 5, 5 6, 6 1, 1 3, 2 4, 3 5, 4 6, 5 1, 6 2

Generalisation of the above for 7 vertices (χ = 4)

7
1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 1, 1 3, 2 4, 3 5, 4 6, 5 7, 6 1, 7 2

Petersen graph (χ = 3)

10
1 2, 2 3, 3 4, 4 5, 5 1, 1 6, 2 7, 3 8, 4 9, 5 10, 6 8, 7 9, 8 10, 9 6, 10 7

Complete graph of 5 vertices, plus disconnected vertex (χ = 5)

6
1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5

Complete graph of 8 vertices (χ = 8)

8
1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, 2 3, 2 4, 2 5, 2 6, 2 7, 2 8, 3 4, 3 5, 3 6, 3 7, 3 8, 4 5, 4 6, 4 7, 4 8, 5 6, 5 7, 5 8, 6 7, 6 8, 7 8

Triangular lattice with 15 vertices (χ = 3)

15
1 2, 1 3, 2 3, 2 4, 2 5, 3 5, 3 6, 4 5, 5 6, 4 7, 4 8, 5 8, 5 9, 6 9, 6 10, 7 8, 8 9, 9 10, 7 11, 7 12, 8 12, 8 13, 9 13, 9 14, 10 14, 10 15, 11 12, 12 13, 13 14, 14 15

Answer 1

Python 2.7 - 122 109 111 109 108 103

f=lambda n,e,m=1:any(all(t*m//m**a%m!=t*m//m**b%m for(a,b)in e)for t in range(m**n))and m or f(n,e,m+1)

Usage:

print f(5, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

Brute force by increasing the chromatic number (m) and check all possible colorings. One coloring can be described as a number in base m. So the possible colorings are 0, 1, ..., m^n-1.

edit: The complete graph of 8 vertices takes quite long. But my laptop solves it in about 10 minutes. The other test cases take only a few seconds.

---

edit 2: Read that preprocessing is allowed, so I let the index of the vertices start with 0: shortens t*m//m**x%m to t//m**a%m (-2). Dissolve lambda and put m into function params (-11)

---

edit 3: preprocessing is not allowed -> back to t*m (+4), simplified // to / (-2).

---

edit 4: remove square brackets in any (-2), thanks xnor.

---

edit 5: instead of taking modulo m twice, simply subtract them and afterwards use modulo (-1). This is also quite a performance improvement. All testcases together take about 25 seconds on my laptop.

---

edit 6: recursive call instead of while 1: and m+=1 (-5). Thanks again, xnor.

Answer 2

Java - 241 218

int k,j,c;int f(int n,int[]e){for(k=1;k<=n;k++)for(long p=0;p<x(n);p++){for(j=0,c=0;j<e.length;c=p%x(e[j])/x(e[j]-1)==p%x(e[j+1])/x(e[j+1]-1)?1:c,j+=2);if(c<1)return k;}return 0;}int x(int a){return(int)Math.pow(k,a);}

The most obvious way to do this given the constraints is brute force. Just step through each chromatic number k, and assign each color to each vertex. If no neighbors are the same color, you have your number. If not, move along.

This takes longest for the test case for χ = 8 (complete graphs suck here), but it's still under 15 seconds (ok, about 100s with latest edit).

Input is the number of vertices n, and an array of edge vertices e[] given in the same order as the OPs comma separated values.

With line breaks:

int k,j,c;
int f(int n,int[]e){
    for(k=1;k<=n;k++)
        for(long p=0;p<x(n);p++){
            for(j=0,c=0;
                j<e.length;
                c=p%x(e[j])/x(e[j]-1)==p%x(e[j+1])/x(e[j+1]-1)?1:c,
                j+=2);
            if(c<1)return k;
        }
    return 0;
}
int x(int a){return(int)Math.pow(k,a);}

Oh, and this assumes the input is some sort of colorable graph. If an edge loops from v1 to v1, or there are no vertices, it can't be colored and will output 0. It will still work for graphs with no edges χ=1, etc.

Answer 3

Python 3 - 162

Uses the same brute-force approach, but uses the itertools library for hopefully faster combination generation. Solves the complete 8-graph in < 1 min on my fairly ordinary machine.

import itertools as I
def c(n,v):
 for i in range(1,n+1):
  for p in I.product(range(i),repeat=n):
   if(0==len([x for x in v if(p[x[0]]==p[x[1]])])):return i

Example usage for the complete 8-graph case:

print(c(8,[x for x in I.combinations(range(8), 2)]))

Answer 4

Haskell, 163 bytes

p x=f(length x)(transpose x)1
f a[b,c]d|or$map(\x->and$g x(h b)(h c))(sequence$replicate a[1..d])=d|0<1=f a b c(d+1)
g a=zipWith(\x y->a!!x/=a!!y)
h=map(flip(-)1)

Usage would be like this:

p [[1, 2],[2, 3],[3, 1]]

Basic brute force approach. Check all the possible coloring combinations if they are valid. Not much else to say here except that I am happy to hear any tips for shortening this even further ;)