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