Find the Chromatic Number 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 &lt; 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
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.