15
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Could you define reasonable? 1 minute? 10? \$\endgroup\$
    – ThreeFx
    Sep 12, 2014 at 16:58
  • \$\begingroup\$ @ThreeFx yes, 10 minutes is reasonable. half a day isn't. I don't want to be too rigorous on the limit, because then I need to test everything on the same (my) machine again. but let's say if it completes within an hour on your machine that's fine. \$\endgroup\$ Sep 12, 2014 at 17:22

4 Answers 4

4
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Nice method. A simple golf: You can remove the brackets in all([...]) if you encase the a,b in parens (which costs no chars here due to spacing) so that the all doesn't mistake them for additional arguments. Also, I suspect you can save chars if you recurse with a function call to the next highest m rather than using a while loop. \$\endgroup\$
    – xnor
    Sep 12, 2014 at 22:02
  • \$\begingroup\$ Thanks, the recursive approach takes +2 chars though. A for m in range(n+1) approach also. \$\endgroup\$
    – Jakube
    Sep 13, 2014 at 9:54
  • \$\begingroup\$ I optimized the recursive approach a bit with any and the and/or trick, and then it saves some chars: 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). \$\endgroup\$
    – xnor
    Sep 13, 2014 at 19:18
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)]))
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
9
  • \$\begingroup\$ I'd say that decrementing the vertices and transposing them counts as "preprocessing". What I had in mind with "any convenient format" was rather that you could choose from flat list, nested list, string, string with convenient delimiters, etc... but the flattened structure should be the same as specified in the challenge. \$\endgroup\$ Sep 12, 2014 at 18:33
  • \$\begingroup\$ @MartinBüttner Alright, I'll change it \$\endgroup\$
    – ThreeFx
    Sep 12, 2014 at 18:34
  • \$\begingroup\$ @ThreeFx all id is the same as and, any id is the same as or and any id$map f list is the same as just any f list. also, you could do a few things with g: you can redefine it as g a=(and.).zipWith(\x y->a!!x/=a!!y), make it infix, change the input order to replace (\x->g x b c) with g b c or even make it completely points-free and inline it. some of these don't work together, so try them all and choose the best one :) \$\endgroup\$ Sep 12, 2014 at 18:36
  • 1
    \$\begingroup\$ @MartinBüttner I think it is fixed, to the cost of maaaaany bytes. :D \$\endgroup\$
    – ThreeFx
    Sep 12, 2014 at 19:28
  • 1
    \$\begingroup\$ How are you solving the 7th example without the number of vertices in the input? \$\endgroup\$ Sep 12, 2014 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.