Graph colouring


A Graph is a collection of nodes (or vertices), connected by edges (or not). Nodes directly connected by edges are called neighbours.

Task
Graph colouring
You are encouraged to solve this task according to the task description, using any language you may know.

In our representation of graphs, nodes are numbered and edges are represented by the two node numbers connected by the edge separated by a dash. Edges define the nodes being connected. Only unconnected nodes need a separate description.

For example,

0-1 1-2 2-0 3

Describes the following graph. Note that node 3 has no neighbours


Example graph
+---+
| 3 |
+---+

  +-------------------+
  |                   |
+---+     +---+     +---+
| 0 | --- | 1 | --- | 2 |
+---+     +---+     +---+

A useful internal datastructure for a graph and for later graph algorithms is as a mapping between each node and the set/list of its neighbours.

In the above example:

0 maps-to 1 and 2
1 maps to 2 and 0
2 maps-to 1 and 0
3 maps-to <nothing>
Graph colouring task

Colour the vertices of a given graph so that no edge is between verticies of the same colour.

  • Integers may be used to denote different colours.
  • Algorithm should do better than just assigning each vertex a separate colour. The idea is to minimise the number of colours used, although no algorithm short of exhaustive search for the minimum is known at present, (and exhaustive search is not a requirement).
  • Show for each edge, the colours assigned on each vertex.
  • Show the total number of nodes, edges, and colours used for each graph.
Use the following graphs
Ex1
       0-1 1-2 2-0 3
+---+
| 3 |
+---+

  +-------------------+
  |                   |
+---+     +---+     +---+
| 0 | --- | 1 | --- | 2 |
+---+     +---+     +---+
Ex2

The wp articles left-side graph

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

  +----------------------------------+
  |                                  |
  |                      +---+       |
  |    +-----------------| 3 | ------+----+
  |    |                 +---+       |    |
  |    |                   |         |    |
  |    |                   |         |    |
  |    |                   |         |    |
  |  +---+     +---+     +---+     +---+  |
  |  | 8 | --- | 1 | --- | 6 | --- | 4 |  |
  |  +---+     +---+     +---+     +---+  |
  |    |         |                   |    |
  |    |         |                   |    |
  |    |         |                   |    |
  |    |       +---+     +---+     +---+  |
  +----+------ | 7 | --- | 2 | --- | 5 | -+
       |       +---+     +---+     +---+
       |                   |
       +-------------------+
Ex3

The wp articles right-side graph which is the same graph as Ex2, but with different node orderings and namings.

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

  +----------------------------------+
  |                                  |
  |                      +---+       |
  |    +-----------------| 5 | ------+----+
  |    |                 +---+       |    |
  |    |                   |         |    |
  |    |                   |         |    |
  |    |                   |         |    |
  |  +---+     +---+     +---+     +---+  |
  |  | 8 | --- | 1 | --- | 4 | --- | 7 |  |
  |  +---+     +---+     +---+     +---+  |
  |    |         |                   |    |
  |    |         |                   |    |
  |    |         |                   |    |
  |    |       +---+     +---+     +---+  |
  +----+------ | 6 | --- | 3 | --- | 2 | -+
       |       +---+     +---+     +---+
       |                   |
       +-------------------+
Ex4

This is the same graph, node naming, and edge order as Ex2 except some of the edges x-y are flipped to y-x. This might alter the node order used in the greedy algorithm leading to differing numbers of colours.

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

                      +-------------------------------------------------+
                      |                                                 |
                      |                                                 |
  +-------------------+---------+                                       |
  |                   |         |                                       |
+---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+
| 4 | --- | 5 | --- | 2 | --- | 7 | --- | 1 | --- | 6 | --- | 3 | --- | 8 |
+---+     +---+     +---+     +---+     +---+     +---+     +---+     +---+
  |         |                             |         |         |         |
  +---------+-----------------------------+---------+         |         |
            |                             |                   |         |
            |                             |                   |         |
            +-----------------------------+-------------------+         |
                                          |                             |
                                          |                             |
                                          +-----------------------------+
References


11lEdit

Translation of: Python
F first_avail_int(data)
   ‘return lowest int 0... not in data’
   V d = Set(data)
   L(i) 0..
      I i !C d
         R i

F greedy_colour(name, connections)
   DefaultDict[Int, [Int]] graph

   L(connection) connections.split(‘ ’)
      I ‘-’ C connection
         V (n1, n2) = connection.split(‘-’).map(Int)
         graph[n1].append(n2)
         graph[n2].append(n1)
      E
         graph[Int(connection)] = [Int]()

   // Greedy colourisation algo
   V order = sorted(graph.keys())
   [Int = Int] colour
   V neighbours = graph
   L(node) order
      V used_neighbour_colours = neighbours[node].filter(nbr -> nbr C @colour).map(nbr -> @colour[nbr])
      colour[node] = first_avail_int(used_neighbour_colours)

   print("\n"name)
   V canonical_edges = Set[(Int, Int)]()
   L(n1, neighbours) sorted(graph.items())
      I !neighbours.empty
         L(n2) neighbours
            V edge = tuple_sorted((n1, n2))
            I edge !C canonical_edges
               print(‘       #.-#.: Colour: #., #.’.format(n1, n2, colour[n1], colour[n2]))
               canonical_edges.add(edge)
      E
         print(‘         #.: Colour: #.’.format(n1, colour[n1]))
   V lc = Set(colour.values()).len
   print("    #Nodes: #.\n    #Edges: #.\n  #Colours: #.".format(colour.len, canonical_edges.len, lc))

L(name, connections) [
      (‘Ex1’, ‘0-1 1-2 2-0 3’),
      (‘Ex2’, ‘1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7’),
      (‘Ex3’, ‘1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6’),
      (‘Ex4’, ‘1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7’)]
   greedy_colour(name, connections)
Output:

Ex1
       0-1: Colour: 0, 1
       0-2: Colour: 0, 2
       1-2: Colour: 1, 2
         3: Colour: 0
    #Nodes: 4
    #Edges: 3
  #Colours: 3

Ex2
       1-6: Colour: 0, 1
       1-7: Colour: 0, 1
       1-8: Colour: 0, 1
       2-5: Colour: 0, 1
       2-7: Colour: 0, 1
       2-8: Colour: 0, 1
       3-5: Colour: 0, 1
       3-6: Colour: 0, 1
       3-8: Colour: 0, 1
       4-5: Colour: 0, 1
       4-6: Colour: 0, 1
       4-7: Colour: 0, 1
    #Nodes: 8
    #Edges: 12
  #Colours: 2

Ex3
       1-4: Colour: 0, 1
       1-6: Colour: 0, 2
       1-8: Colour: 0, 3
       2-3: Colour: 0, 1
       2-5: Colour: 0, 2
       2-7: Colour: 0, 3
       3-6: Colour: 1, 2
       3-8: Colour: 1, 3
       4-5: Colour: 1, 2
       4-7: Colour: 1, 3
       5-8: Colour: 2, 3
       6-7: Colour: 2, 3
    #Nodes: 8
    #Edges: 12
  #Colours: 4

Ex4
       1-6: Colour: 0, 1
       1-7: Colour: 0, 1
       1-8: Colour: 0, 1
       2-5: Colour: 0, 1
       2-7: Colour: 0, 1
       2-8: Colour: 0, 1
       3-5: Colour: 0, 1
       3-6: Colour: 0, 1
       3-8: Colour: 0, 1
       4-5: Colour: 0, 1
       4-6: Colour: 0, 1
       4-7: Colour: 0, 1
    #Nodes: 8
    #Edges: 12
  #Colours: 2

GoEdit

As mentioned in the task description, there is no known efficient algorithm which can guarantee that a minimum number of colors is used for a given graph. The following uses both the so-called 'greedy' algorithm (as described here) and the Welsh-Powell algorithm (as described here), suitably adjusted to the needs of this task.

The results are exactly the same for both algorithms. Whilst one would normally expect Welsh-Powell to give better results overall, the last three examples are not well suited to it as each node has exactly the same number of neighbors i.e. the valences are equal.

The results agree with the Python entry for examples 1 and 2 but, for example 3, Python gives 2 colors compared to my 4 and, for example 4, Python gives 3 colors compared to my 2.

package main

import (
    "fmt"
    "sort"
)

type graph struct {
    nn  int     // number of nodes
    st  int     // node numbering starts from
    nbr [][]int // neighbor list for each node
}

type nodeval struct {
    n int // number of node
    v int // valence of node i.e. number of neighbors
}

func contains(s []int, n int) bool {
    for _, e := range s {
        if e == n {
            return true
        }
    }
    return false
}

func newGraph(nn, st int) graph {
    nbr := make([][]int, nn)
    return graph{nn, st, nbr}
}

// Note that this creates a single 'virtual' edge for an isolated node.
func (g graph) addEdge(n1, n2 int) {
    n1, n2 = n1-g.st, n2-g.st // adjust to starting node number
    g.nbr[n1] = append(g.nbr[n1], n2)
    if n1 != n2 {
        g.nbr[n2] = append(g.nbr[n2], n1)
    }
}

// Uses 'greedy' algorithm.
func (g graph) greedyColoring() []int {
    // create a slice with a color for each node, starting with color 0
    cols := make([]int, g.nn) // all zero by default including the first node
    for i := 1; i < g.nn; i++ {
        cols[i] = -1 // mark all nodes after the first as having no color assigned (-1)
    }
    // create a bool slice to keep track of which colors are available
    available := make([]bool, g.nn) // all false by default
    // assign colors to all nodes after the first
    for i := 1; i < g.nn; i++ {
        // iterate through neighbors and mark their colors as available
        for _, j := range g.nbr[i] {
            if cols[j] != -1 {
                available[cols[j]] = true
            }
        }
        // find the first available color
        c := 0
        for ; c < g.nn; c++ {
            if !available[c] {
                break
            }
        }
        cols[i] = c // assign it to the current node
        // reset the neighbors' colors to unavailable
        // before the next iteration
        for _, j := range g.nbr[i] {
            if cols[j] != -1 {
                available[cols[j]] = false
            }
        }
    }
    return cols
}

// Uses Welsh-Powell algorithm.
func (g graph) wpColoring() []int {
    // create nodeval for each node
    nvs := make([]nodeval, g.nn)
    for i := 0; i < g.nn; i++ {
        v := len(g.nbr[i])
        if v == 1 && g.nbr[i][0] == i { // isolated node
            v = 0
        }
        nvs[i] = nodeval{i, v}
    }
    // sort the nodevals in descending order by valence
    sort.Slice(nvs, func(i, j int) bool {
        return nvs[i].v > nvs[j].v
    })
    // create colors slice with entries for each node
    cols := make([]int, g.nn)
    for i := range cols {
        cols[i] = -1 // set all nodes to no color (-1) initially
    }
    currCol := 0 // start with color 0
    for f := 0; f < g.nn-1; f++ {
        h := nvs[f].n
        if cols[h] != -1 { // already assigned a color
            continue
        }
        cols[h] = currCol
        // assign same color to all subsequent uncolored nodes which are
        // not connected to a previous colored one
    outer:
        for i := f + 1; i < g.nn; i++ {
            j := nvs[i].n
            if cols[j] != -1 { // already colored
                continue
            }
            for k := f; k < i; k++ {
                l := nvs[k].n
                if cols[l] == -1 { // not yet colored
                    continue
                }
                if contains(g.nbr[j], l) {
                    continue outer // node j is connected to an earlier colored node
                }
            }
            cols[j] = currCol
        }
        currCol++
    }
    return cols
}

func main() {
    fns := [](func(graph) []int){graph.greedyColoring, graph.wpColoring}
    titles := []string{"'Greedy'", "Welsh-Powell"}
    nns := []int{4, 8, 8, 8}
    starts := []int{0, 1, 1, 1}
    edges1 := [][2]int{{0, 1}, {1, 2}, {2, 0}, {3, 3}}
    edges2 := [][2]int{{1, 6}, {1, 7}, {1, 8}, {2, 5}, {2, 7}, {2, 8},
        {3, 5}, {3, 6}, {3, 8}, {4, 5}, {4, 6}, {4, 7}}
    edges3 := [][2]int{{1, 4}, {1, 6}, {1, 8}, {3, 2}, {3, 6}, {3, 8},
        {5, 2}, {5, 4}, {5, 8}, {7, 2}, {7, 4}, {7, 6}}
    edges4 := [][2]int{{1, 6}, {7, 1}, {8, 1}, {5, 2}, {2, 7}, {2, 8},
        {3, 5}, {6, 3}, {3, 8}, {4, 5}, {4, 6}, {4, 7}}
    for j, fn := range fns {
        fmt.Println("Using the", titles[j], "algorithm:\n")
        for i, edges := range [][][2]int{edges1, edges2, edges3, edges4} {
            fmt.Println("  Example", i+1)
            g := newGraph(nns[i], starts[i])
            for _, e := range edges {
                g.addEdge(e[0], e[1])
            }
            cols := fn(g)
            ecount := 0 // counts edges
            for _, e := range edges {
                if e[0] != e[1] {
                    fmt.Printf("    Edge  %d-%d -> Color %d, %d\n", e[0], e[1],
                        cols[e[0]-g.st], cols[e[1]-g.st])
                    ecount++
                } else {
                    fmt.Printf("    Node  %d   -> Color %d\n", e[0], cols[e[0]-g.st])
                }
            }
            maxCol := 0 // maximum color number used
            for _, col := range cols {
                if col > maxCol {
                    maxCol = col
                }
            }
            fmt.Println("    Number of nodes  :", nns[i])
            fmt.Println("    Number of edges  :", ecount)
            fmt.Println("    Number of colors :", maxCol+1)
            fmt.Println()
        }
    }
}
Output:
Using the 'Greedy' algorithm:

  Example 1
    Edge  0-1 -> Color 0, 1
    Edge  1-2 -> Color 1, 2
    Edge  2-0 -> Color 2, 0
    Node  3   -> Color 0
    Number of nodes  : 4
    Number of edges  : 3
    Number of colors : 3

  Example 2
    Edge  1-6 -> Color 0, 1
    Edge  1-7 -> Color 0, 1
    Edge  1-8 -> Color 0, 1
    Edge  2-5 -> Color 0, 1
    Edge  2-7 -> Color 0, 1
    Edge  2-8 -> Color 0, 1
    Edge  3-5 -> Color 0, 1
    Edge  3-6 -> Color 0, 1
    Edge  3-8 -> Color 0, 1
    Edge  4-5 -> Color 0, 1
    Edge  4-6 -> Color 0, 1
    Edge  4-7 -> Color 0, 1
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 2

  Example 3
    Edge  1-4 -> Color 0, 1
    Edge  1-6 -> Color 0, 2
    Edge  1-8 -> Color 0, 3
    Edge  3-2 -> Color 1, 0
    Edge  3-6 -> Color 1, 2
    Edge  3-8 -> Color 1, 3
    Edge  5-2 -> Color 2, 0
    Edge  5-4 -> Color 2, 1
    Edge  5-8 -> Color 2, 3
    Edge  7-2 -> Color 3, 0
    Edge  7-4 -> Color 3, 1
    Edge  7-6 -> Color 3, 2
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 4

  Example 4
    Edge  1-6 -> Color 0, 1
    Edge  7-1 -> Color 1, 0
    Edge  8-1 -> Color 1, 0
    Edge  5-2 -> Color 1, 0
    Edge  2-7 -> Color 0, 1
    Edge  2-8 -> Color 0, 1
    Edge  3-5 -> Color 0, 1
    Edge  6-3 -> Color 1, 0
    Edge  3-8 -> Color 0, 1
    Edge  4-5 -> Color 0, 1
    Edge  4-6 -> Color 0, 1
    Edge  4-7 -> Color 0, 1
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 2

Using the Welsh-Powell algorithm:

  Example 1
    Edge  0-1 -> Color 0, 1
    Edge  1-2 -> Color 1, 2
    Edge  2-0 -> Color 2, 0
    Node  3   -> Color 0
    Number of nodes  : 4
    Number of edges  : 3
    Number of colors : 3

  Example 2
    Edge  1-6 -> Color 0, 1
    Edge  1-7 -> Color 0, 1
    Edge  1-8 -> Color 0, 1
    Edge  2-5 -> Color 0, 1
    Edge  2-7 -> Color 0, 1
    Edge  2-8 -> Color 0, 1
    Edge  3-5 -> Color 0, 1
    Edge  3-6 -> Color 0, 1
    Edge  3-8 -> Color 0, 1
    Edge  4-5 -> Color 0, 1
    Edge  4-6 -> Color 0, 1
    Edge  4-7 -> Color 0, 1
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 2

  Example 3
    Edge  1-4 -> Color 0, 1
    Edge  1-6 -> Color 0, 2
    Edge  1-8 -> Color 0, 3
    Edge  3-2 -> Color 1, 0
    Edge  3-6 -> Color 1, 2
    Edge  3-8 -> Color 1, 3
    Edge  5-2 -> Color 2, 0
    Edge  5-4 -> Color 2, 1
    Edge  5-8 -> Color 2, 3
    Edge  7-2 -> Color 3, 0
    Edge  7-4 -> Color 3, 1
    Edge  7-6 -> Color 3, 2
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 4

  Example 4
    Edge  1-6 -> Color 0, 1
    Edge  7-1 -> Color 1, 0
    Edge  8-1 -> Color 1, 0
    Edge  5-2 -> Color 1, 0
    Edge  2-7 -> Color 0, 1
    Edge  2-8 -> Color 0, 1
    Edge  3-5 -> Color 0, 1
    Edge  6-3 -> Color 1, 0
    Edge  3-8 -> Color 0, 1
    Edge  4-5 -> Color 0, 1
    Edge  4-6 -> Color 0, 1
    Edge  4-7 -> Color 0, 1
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 2

HaskellEdit

import Data.Maybe
import Data.List
import Control.Monad.State
import qualified Data.Map as M
import Text.Printf

------------------------------------------------------------
-- Primitive graph representation

type Node = Int
type Color = Int
type Graph = M.Map Node [Node]

nodes :: Graph -> [Node]
nodes = M.keys

adjacentNodes :: Graph -> Node -> [Node]
adjacentNodes g n = fromMaybe [] $ M.lookup n g 

degree :: Graph -> Node -> Int 
degree g = length . adjacentNodes g

fromList :: [(Node, [Node])] -> Graph
fromList  = foldr add M.empty
  where
    add (a, bs) g = foldr (join [a]) (join bs a g) bs
    join = flip (M.insertWith (++))

readGraph :: String -> Graph
readGraph = fromList . map interprete . words
  where
    interprete s = case span (/= '-') s of
      (a, "") -> (read a, [])
      (a, '-':b) -> (read a, [read b])

------------------------------------------------------------
-- Graph coloring functions

uncolored :: Node -> State [(Node, Color)] Bool
uncolored n = isNothing <$> colorOf n

colorOf :: Node -> State [(Node, Color)] (Maybe Color)
colorOf n = gets (lookup n)

greedyColoring :: Graph -> [(Node, Color)]
greedyColoring g = mapM_ go (nodes g) `execState` []
  where
    go n = do
      c <- colorOf n
      when (isNothing c) $ do
        adjacentColors <- nub . catMaybes <$> mapM colorOf (adjacentNodes g n)
        let newColor = head $ filter (`notElem` adjacentColors) [1..]
        modify ((n, newColor) :)
      filterM uncolored (adjacentNodes g n) >>= mapM_ go

wpColoring :: Graph -> [(Node, Color)]
wpColoring g = go [1..] nodesList `execState` []
  where
    nodesList = sortOn (negate . degree g) (nodes g)

    go _ [] = pure ()
    go (c:cs) ns = do 
      mark c ns 
      filterM uncolored ns >>= go cs

    mark c [] = pure () :: State [(Node, Color)] ()
    mark c (n:ns) = do 
      modify ((n, c) :) 
      mark c (filter (`notElem` adjacentNodes g n) ns)

Simple usage examples:

λ> let g = fromList [(1,[2,3]),(2,[3,4]),(4,[3,5])]

λ> g
fromList [(1,[2,3]),(2,[1,3,4]),(3,[1,2,4]),(4,[2,3,5]),(5,[4])]

λ> greedyColoring g
[(5,2),(4,1),(3,3),(2,2),(1,1)]

λ> wpColoring g
[(1,3),(4,3),(3,2),(5,1),(2,1)]

The task:

ex1 = "0-1 1-2 2-0 3"
ex2 = "1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"
ex3 = "1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"
ex4 = "1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"

task method ex =
  let g = readGraph ex
      cs = sortOn fst $ method g
      color n = fromJust $ lookup n cs
      ns = nodes g
      mkLine n = printf "%d\t%d\t%s\n" n (color n) (show (color <$> adjacentNodes g n))
  in do
    print ex
    putStrLn $ "nodes:\t" ++ show ns
    putStrLn $ "colors:\t" ++ show (nub (snd <$> cs))
    putStrLn "node\tcolor\tadjacent colors"
    mapM_ mkLine ns
    putStrLn ""

Runing greedy algorithm:

λ> mapM_ (task greedyColoring) [ex1,ex2,ex3,ex4]
"0-1 1-2 2-0 3"
nodes:	[0,1,2,3]
colors:	[1,2,3]
node	color	adjacent colors
0	1	[2,3]
1	2	[1,3]
2	3	[2,1]
3	1	[]

"1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"
nodes:	[1,2,3,4,5,6,7,8]
colors:	[1,2]
node	color	adjacent colors
1	1	[2,2,2]
2	1	[2,2,2]
3	1	[2,2,2]
4	1	[2,2,2]
5	2	[1,1,1]
6	2	[1,1,1]
7	2	[1,1,1]
8	2	[1,1,1]

"1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"
nodes:	[1,2,3,4,5,6,7,8]
colors:	[1,2]
node	color	adjacent colors
1	1	[2,2,2]
2	2	[1,1,1]
3	1	[2,2,2]
4	2	[1,1,1]
5	1	[2,2,2]
6	2	[1,1,1]
7	1	[2,2,2]
8	2	[1,1,1]

"1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"
nodes:	[1,2,3,4,5,6,7,8]
colors:	[1,2]
node	color	adjacent colors
1	1	[2,2,2]
2	1	[2,2,2]
3	1	[2,2,2]
4	1	[2,2,2]
5	2	[1,1,1]
6	2	[1,1,1]
7	2	[1,1,1]
8	2	[1,1,1] 

Runing Welsh-Powell algorithm:

λ> mapM_ (task wpColoring) [ex1,ex2,ex3,ex4]
"0-1 1-2 2-0 3"
nodes:	[0,1,2,3]
colors:	[1,2,3]
node	color	adjacent colors
0	1	[2,3]
1	2	[1,3]
2	3	[2,1]
3	1	[]

"1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"
nodes:	[1,2,3,4,5,6,7,8]
colors:	[1,2]
node	color	adjacent colors
1	1	[2,2,2]
2	1	[2,2,2]
3	1	[2,2,2]
4	1	[2,2,2]
5	2	[1,1,1]
6	2	[1,1,1]
7	2	[1,1,1]
8	2	[1,1,1]

"1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"
nodes:	[1,2,3,4,5,6,7,8]
colors:	[1,2,3,4]
node	color	adjacent colors
1	1	[2,3,4]
2	1	[2,3,4]
3	2	[1,3,4]
4	2	[1,3,4]
5	3	[1,2,4]
6	3	[1,2,4]
7	4	[1,2,3]
8	4	[1,2,3]

"1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"
nodes:	[1,2,3,4,5,6,7,8]
colors:	[1,2]
node	color	adjacent colors
1	1	[2,2,2]
2	1	[2,2,2]
3	1	[2,2,2]
4	1	[2,2,2]
5	2	[1,1,1]
6	2	[1,1,1]
7	2	[1,1,1]
8	2	[1,1,1]

JEdit

Greedy coloring satisfies the task requirements.

parse=: {{
  ref=: 2$L:1(;:each cut y) -.L:1 ;:'-'
  labels=: /:~~.;ref
  sparse=. (*:#labels) > 20*#ref
  graph=: (+.|:) 1 (labels i.L:1 ref)} $.^:sparse 0$~2##labels
}}

greedy=: {{
  colors=. (#y)#a:
  for_node.y do.
    color=. <{.(-.~ [:i.1+#) ~.;node#colors
    colors=. color node_index} colors
  end.
  ;colors
}}

To display colors for edges, we show the graph specification and beneath the representation of each edge A-B we show colorA:colorB.

ex1=:'0-1 1-2 2-0 3'
ex2=:'1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7'
ex3=:'1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6'
ex4=:'1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7'
require'format/printf'
require'format/printf'
task=: {{
  colors=. greedy parse y
  echo'nodes: %d, edges: %d, colours: %d' sprintf #each graph;ref;~.colors
  edgecolors=. <@(,&":':',&":])/"1(>labels i.L:1 ref){colors
  ,./>' ',.~each^:2(cut y),:each edgecolors
}}

   task ex1
nodes: 4, edges: 4, colours: 3
0-1  1-2  2-0  3    
0:1  1:2  2:0  0:0  
   
   task ex2
nodes: 8, edges: 12, colours: 2
1-6  1-7  1-8  2-5  2-7  2-8  3-5  3-6  3-8  4-5  4-6  4-7  
0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  
   
   task ex3
nodes: 8, edges: 12, colours: 4
1-4  1-6  1-8  3-2  3-6  3-8  5-2  5-4  5-8  7-2  7-4  7-6  
0:1  0:2  0:3  1:0  1:2  1:3  2:0  2:1  2:3  3:0  3:1  3:2  
   
   task ex4
nodes: 8, edges: 12, colours: 2
1-6  7-1  8-1  5-2  2-7  2-8  3-5  6-3  3-8  4-5  4-6  4-7  
0:1  1:0  1:0  1:0  0:1  0:1  0:1  1:0  0:1  0:1  0:1  0:1

But, of course, we can do better than that. For example, we can try a few random ordered greedy color assignments, retaining a color assignment with the fewest colors:

anneal=: {{
  best=. i.#y [ cost=. #~.greedy y
  for.i.#y do.
    o=. ?~#y
    c=.#~.greedy o ([ { {"1) y
    if. cost > c do.
      best=. o [ cost=. c
    end.
  end.
  (/:best) { greedy best ([ { {"1) y
}}
task=: {{
  colors=. anneal parse y
  echo'nodes: %d, edges: %d, colours: %d' sprintf #each graph;ref;~.colors
  edgecolors=. <@(,&":':',&":])/"1(>labels i.L:1 ref){colors
  ,./>' ',.~each^:2(cut y),:each edgecolors
}}

   task ex1
nodes: 4, edges: 4, colours: 3
0-1  1-2  2-0  3    
0:1  1:2  2:0  0:0  
   
   task ex2
nodes: 8, edges: 12, colours: 2
1-6  1-7  1-8  2-5  2-7  2-8  3-5  3-6  3-8  4-5  4-6  4-7  
0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  
   
   task ex3
nodes: 8, edges: 12, colours: 2
1-4  1-6  1-8  3-2  3-6  3-8  5-2  5-4  5-8  7-2  7-4  7-6  
0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  0:1  
   
   task ex4
nodes: 8, edges: 12, colours: 2
1-6  7-1  8-1  5-2  2-7  2-8  3-5  6-3  3-8  4-5  4-6  4-7  
0:1  1:0  1:0  1:0  0:1  0:1  0:1  1:0  0:1  0:1  0:1  0:1

JuliaEdit

Uses a repeated randomization of node color ordering to seek a minimum number of colors needed.

using Random

"""Useful constants for the colors to be selected for nodes of the graph"""
const colors4 = ["blue", "red", "green", "yellow"]
const badcolor = "black"
@assert(!(badcolor in colors4))

"""
    struct graph

undirected simple graph
constructed from its name and a string listing of point to point connections
"""
mutable struct Graph
    name::String
    g::Dict{Int, Vector{Int}}
    nodecolor::Dict{Int, String}
    function Graph(nam::String, s::String)
        gdic = Dict{Int, Vector{Int}}()
        for p in eachmatch(r"(\d+)-(\d+)|(\d+)(?!\s*-)" , s)
            if p != nothing
                if p[3] != nothing
                    n3 = parse(Int, p[3])
                    get!(gdic, n3, [])
                else
                    n1, n2 = parse(Int, p[1]), parse(Int, p[2])
                    p1vec = get!(gdic, n1, [])
                    !(n2 in p1vec) && push!(p1vec, n2)
                    p2vec = get!(gdic, n2, [])
                    !(n1 in p2vec) && push!(p2vec, n1)
                end
            end
        end
        new(nam, gdic, Dict{Int, String}())
    end
end

"""
    tryNcolors!(gr::Graph, N, maxtrials)

Try up to maxtrials to get a coloring with <= N colors
"""
function tryNcolors!(gr::Graph, N, maxtrials)
    t, mintrial, minord = N, N + 1, Dict()
    for _ in 1:maxtrials
        empty!(gr.nodecolor)
        ordering = shuffle(collect(keys(gr.g)))
        for node in ordering
            usedneighborcolors = [gr.nodecolor[c] for c in gr.g[node] if haskey(gr.nodecolor, c)]
            gr.nodecolor[node] = badcolor
            for c in colors4[1:N]
                if !(c in usedneighborcolors)
                    gr.nodecolor[node] = c
                    break
                end
            end
        end
        t = length(unique(values(gr.nodecolor)))
        if t < mintrial
            mintrial = t
            minord = deepcopy(gr.nodecolor)
        end
    end
    if length(minord) > 0
        gr.nodecolor = minord
    end
end


"""
    prettyprintcolors(gr::graph)

print out the colored nodes in graph
"""
function prettyprintcolors(gr::Graph)
    println("\nColors for the graph named ", gr.name, ":")
    edgesdone = Vector{Vector{Int}}()
    for (node, neighbors) in gr.g
        if !isempty(neighbors)
            for n in neighbors
                edge = node < n ? [node, n] : [n, node]
                if !(edge in edgesdone)
                    println("    ", edge[1], "-", edge[2], " Color: ",
                        gr.nodecolor[edge[1]], ", ", gr.nodecolor[edge[2]])
                    push!(edgesdone, edge)
                end
            end
        else
            println("    ", node, ": ", gr.nodecolor[node])
        end
    end
    println("\n", length(unique(keys(gr.nodecolor))), " nodes, ",
        length(edgesdone), " edges, ",
        length(unique(values(gr.nodecolor))), " colors.")
end

for (name, txt) in [("Ex1", "0-1 1-2 2-0 3"),
    ("Ex2", "1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"),
    ("Ex3", "1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"),
    ("Ex4", "1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7")]
    exgraph = Graph(name, txt)
    tryNcolors!(exgraph, 4, 100)
    prettyprintcolors(exgraph)
end
Output:
Colors for the graph named Ex1:
    0-1 Color: red, blue
    0-2 Color: red, green
    1-2 Color: blue, green
    3: blue

4 nodes, 3 edges, 3 colors.

Colors for the graph named Ex2:
    1-7 Color: blue, red
    2-7 Color: blue, red
    4-7 Color: blue, red
    4-5 Color: blue, red
    4-6 Color: blue, red
    2-5 Color: blue, red
    2-8 Color: blue, red
    3-5 Color: blue, red
    3-6 Color: blue, red
    3-8 Color: blue, red
    1-8 Color: blue, red
    1-6 Color: blue, red

8 nodes, 12 edges, 2 colors.

Colors for the graph named Ex3:
    2-7 Color: red, blue
    4-7 Color: red, blue
    6-7 Color: red, blue
    1-4 Color: blue, red
    4-5 Color: red, blue
    2-3 Color: red, blue
    2-5 Color: red, blue
    3-6 Color: blue, red
    3-8 Color: blue, red
    1-8 Color: blue, red
    5-8 Color: blue, red
    1-6 Color: blue, red

8 nodes, 12 edges, 2 colors.

Colors for the graph named Ex4:
    1-7 Color: blue, red
    2-7 Color: blue, red
    4-7 Color: blue, red
    4-5 Color: blue, red
    4-6 Color: blue, red
    2-5 Color: blue, red
    2-8 Color: blue, red
    3-5 Color: blue, red
    3-6 Color: blue, red
    3-8 Color: blue, red
    1-8 Color: blue, red
    1-6 Color: blue, red

8 nodes, 12 edges, 2 colors.

Mathematica / Wolfram LanguageEdit

ClearAll[ColorGroups]
ColorGroups[g_Graph] := Module[{h, cols, indset, diffcols},
  h = g;
  cols = {};
  While[! EmptyGraphQ[h], maxd = RandomChoice[VertexList[h]];
   indset = Flatten[FindIndependentVertexSet[{h, maxd}]];
   AppendTo[cols, indset];
   h = VertexDelete[h, indset];
   ];
  AppendTo[cols, VertexList[h]];
  diffcols = Length[cols];
  cols = Catenate[Map[Thread][Rule @@@ Transpose[{cols, Range[Length[cols]]}]]];
  Print[Column[Row[{"Edge ", #1, " to ", #2, " has colors ", #1 /. cols, " and ", #2 /. cols }] & @@@ EdgeList[g]]];
  Print[Grid[{{"Vertices: ", VertexCount[g]}, {"Edges: ", EdgeCount[g]}, {"Colors used: ", diffcols}}]]
  ]
ColorGroups[Graph[Range[0, 3], {0 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 2, 
   2 \[UndirectedEdge] 0}]]
ColorGroups[Graph[Range[8], {1 \[UndirectedEdge] 6, 1 \[UndirectedEdge] 7, 
   1 \[UndirectedEdge] 8, 2 \[UndirectedEdge] 5, 
   2 \[UndirectedEdge] 7, 2 \[UndirectedEdge] 8, 
   3 \[UndirectedEdge] 5, 3 \[UndirectedEdge] 6, 
   3 \[UndirectedEdge] 8, 4 \[UndirectedEdge] 5, 
   4 \[UndirectedEdge] 6, 4 \[UndirectedEdge] 7}]]
ColorGroups[Graph[Range[8], {1 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 6, 
   1 \[UndirectedEdge] 8, 3 \[UndirectedEdge] 2, 
   3 \[UndirectedEdge] 6, 3 \[UndirectedEdge] 8, 
   5 \[UndirectedEdge] 2, 5 \[UndirectedEdge] 4, 
   5 \[UndirectedEdge] 8, 7 \[UndirectedEdge] 2, 
   7 \[UndirectedEdge] 4, 7 \[UndirectedEdge] 6}]]
ColorGroups[Graph[Range[8], {1 \[UndirectedEdge] 6, 7 \[UndirectedEdge] 1, 
   8 \[UndirectedEdge] 1, 5 \[UndirectedEdge] 2, 
   2 \[UndirectedEdge] 7, 2 \[UndirectedEdge] 8, 
   3 \[UndirectedEdge] 5, 6 \[UndirectedEdge] 3, 
   3 \[UndirectedEdge] 8, 4 \[UndirectedEdge] 5, 
   4 \[UndirectedEdge] 6, 4 \[UndirectedEdge] 7}]]
Output:
Edge 0 to 1 has colors 1 and 3
Edge 1 to 2 has colors 3 and 2
Edge 2 to 0 has colors 2 and 1
Vertices: 	4
Edges: 	3
Colors used: 	3

Edge 1 to 6 has colors 1 and 2
Edge 1 to 7 has colors 1 and 2
Edge 1 to 8 has colors 1 and 2
Edge 2 to 5 has colors 1 and 2
Edge 2 to 7 has colors 1 and 2
Edge 2 to 8 has colors 1 and 2
Edge 3 to 5 has colors 1 and 2
Edge 3 to 6 has colors 1 and 2
Edge 3 to 8 has colors 1 and 2
Edge 4 to 5 has colors 1 and 2
Edge 4 to 6 has colors 1 and 2
Edge 4 to 7 has colors 1 and 2
Vertices: 	8
Edges: 	12
Colors used: 	2

Edge 1 to 4 has colors 1 and 2
Edge 1 to 6 has colors 1 and 2
Edge 1 to 8 has colors 1 and 2
Edge 3 to 2 has colors 1 and 2
Edge 3 to 6 has colors 1 and 2
Edge 3 to 8 has colors 1 and 2
Edge 5 to 2 has colors 1 and 2
Edge 5 to 4 has colors 1 and 2
Edge 5 to 8 has colors 1 and 2
Edge 7 to 2 has colors 1 and 2
Edge 7 to 4 has colors 1 and 2
Edge 7 to 6 has colors 1 and 2
Vertices: 	8
Edges: 	12
Colors used: 	2

Edge 1 to 6 has colors 2 and 1
Edge 7 to 1 has colors 1 and 2
Edge 8 to 1 has colors 1 and 2
Edge 5 to 2 has colors 1 and 2
Edge 2 to 7 has colors 2 and 1
Edge 2 to 8 has colors 2 and 1
Edge 3 to 5 has colors 2 and 1
Edge 6 to 3 has colors 1 and 2
Edge 3 to 8 has colors 2 and 1
Edge 4 to 5 has colors 2 and 1
Edge 4 to 6 has colors 2 and 1
Edge 4 to 7 has colors 2 and 1
Vertices: 	8
Edges: 	12
Colors used: 	2

NimEdit

We use the “DSatur” algorithm described here: https://en.wikipedia.org/wiki/DSatur.

For the four examples, it gives the minimal number of colors.

import algorithm, sequtils, strscans, strutils, tables

const NoColor = 0

type

  Color = range[0..63]

  Node = ref object
    num: Natural          # Node number.
    color: Color          # Node color.
    degree: Natural       # Node degree.
    dsat: Natural         # Node Dsaturation.
    neighbors: seq[Node]  # List of neighbors.

  Graph = seq[Node]       # List of nodes ordered by number.

#---------------------------------------------------------------------------------------------------

proc initGraph(graphRepr: string): Graph =
  ## Initialize the graph from its string representation.

  var mapping: Table[Natural, Node]   # Temporary mapping.
  for elem in graphRepr.splitWhitespace():
    var num1, num2: int
    if elem.scanf("$i-$i", num1, num2):
      let node1 = mapping.mgetOrPut(num1, Node(num: num1))
      let node2 = mapping.mgetOrPut(num2, Node(num: num2))
      node1.neighbors.add node2
      node2.neighbors.add node1
    elif elem.scanf("$i", num1):
      discard mapping.mgetOrPut(num1, Node(num: num1))
    else:
      raise newException(ValueError, "wrong description: " & elem)

  for node in mapping.values:
    node.degree = node.neighbors.len
  result = sortedByIt(toSeq(mapping.values), it.num)

#---------------------------------------------------------------------------------------------------

proc numbers(nodes: seq[Node]): string =
  ## Return the numbers of a list of nodes.
  for node in nodes:
    result.addSep(" ")
    result.add($node.num)

#---------------------------------------------------------------------------------------------------

proc `$`(graph: Graph): string =
  ## Return the description of the graph.

  var maxColor = NoColor
  for node in graph:
    stdout.write "Node ", node.num, ":   color = ", node.color
    if node.color > maxColor: maxColor = node.color
    if node.neighbors.len > 0:
      echo "   neighbors = ", sortedByIt(node.neighbors, it.num).numbers
    else:
      echo ""
  echo "Number of colors: ", maxColor

#---------------------------------------------------------------------------------------------------

proc `<`(node1, node2: Node): bool =
  ## Comparison of nodes, by dsaturation first, then by degree.
  if node1.dsat == node2.dsat: node1.degree < node2.degree
  else: node1.dsat < node2.dsat

#---------------------------------------------------------------------------------------------------

proc getMaxDsatNode(nodes: var seq[Node]): Node =
  ## Return the node with the greatest dsaturation.
  let idx = nodes.maxIndex()
  result = nodes[idx]
  nodes.delete(idx)

#---------------------------------------------------------------------------------------------------

proc minColor(node: Node): COLOR =
  ## Return the minimum available color for a node.
  var colorUsed: set[Color]
  for neighbor in node.neighbors:
    colorUsed.incl neighbor.color
  for color in 1..Color.high:
    if color notin colorUsed: return color

#---------------------------------------------------------------------------------------------------

proc distinctColorsCount(node: Node): Natural =
  ## Return the number of distinct colors of the neighbors of a node.
  var colorUsed: set[Color]
  for neighbor in node.neighbors:
    colorUsed.incl neighbor.color
  result = colorUsed.card

#---------------------------------------------------------------------------------------------------

proc updateDsats(node: Node) =
  ## Update the dsaturations of the neighbors of a node.
  for neighbor in node.neighbors:
    if neighbor.color == NoColor:
      neighbor.dsat = neighbor.distinctColorsCount()

#---------------------------------------------------------------------------------------------------

proc colorize(graphRepr: string) =
  ## Colorize a graph.

  let graph = initGraph(graphRepr)
  var nodes = sortedByIt(graph, -it.degree)   # Copy or graph sorted by decreasing degrees.
  while nodes.len > 0:
    let node = nodes.getMaxDsatNode()
    node.color = node.minColor()
    node.updateDsats()

  echo "Graph: ", graphRepr
  echo graph


#---------------------------------------------------------------------------------------------------

when isMainModule:
  colorize("0-1 1-2 2-0 3")
  colorize("1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7")
  colorize("1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6")
  colorize("1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7")
Output:
Graph: 0-1 1-2 2-0 3
Node 0:   color = 1   neighbors = 1 2
Node 1:   color = 2   neighbors = 0 2
Node 2:   color = 3   neighbors = 0 1
Node 3:   color = 1
Number of colors: 3

Graph: 1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
Node 1:   color = 1   neighbors = 6 7 8
Node 2:   color = 1   neighbors = 5 7 8
Node 3:   color = 1   neighbors = 5 6 8
Node 4:   color = 1   neighbors = 5 6 7
Node 5:   color = 2   neighbors = 2 3 4
Node 6:   color = 2   neighbors = 1 3 4
Node 7:   color = 2   neighbors = 1 2 4
Node 8:   color = 2   neighbors = 1 2 3
Number of colors: 2

Graph: 1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
Node 1:   color = 1   neighbors = 4 6 8
Node 2:   color = 2   neighbors = 3 5 7
Node 3:   color = 1   neighbors = 2 6 8
Node 4:   color = 2   neighbors = 1 5 7
Node 5:   color = 1   neighbors = 2 4 8
Node 6:   color = 2   neighbors = 1 3 7
Node 7:   color = 1   neighbors = 2 4 6
Node 8:   color = 2   neighbors = 1 3 5
Number of colors: 2

Graph: 1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
Node 1:   color = 1   neighbors = 6 7 8
Node 2:   color = 1   neighbors = 5 7 8
Node 3:   color = 1   neighbors = 5 6 8
Node 4:   color = 1   neighbors = 5 6 7
Node 5:   color = 2   neighbors = 2 3 4
Node 6:   color = 2   neighbors = 1 3 4
Node 7:   color = 2   neighbors = 1 2 4
Node 8:   color = 2   neighbors = 1 2 3
Number of colors: 2

PerlEdit

Translation of: Raku
use strict;
use warnings;
no warnings 'uninitialized';
use feature 'say';
use constant True => 1;
use List::Util qw(head uniq);

sub GraphNodeColor {
    my(%OneMany, %NodeColor, %NodePool, @ColorPool);
    my(@data) = @_;

    for (@data) {
        my($a,$b) = @$_;
        push @{$OneMany{$a}}, $b;
        push @{$OneMany{$b}}, $a;
    }

    @ColorPool = 0 .. -1 + scalar %OneMany;
    $NodePool{$_} = True for keys %OneMany;

    if ($OneMany{''}) { # skip islanders for now
        delete $NodePool{$_} for @{$OneMany{''}};
        delete $NodePool{''};
    }

    while (%NodePool) {
        my $color = shift @ColorPool;
        my %TempPool = %NodePool;

        while (my $n = head 1, sort keys %TempPool) {
            $NodeColor{$n} = $color;
            delete $TempPool{$n};
            delete $TempPool{$_} for @{$OneMany{$n}} ; # skip neighbors as well
            delete $NodePool{$n};
        }

        if ($OneMany{''}) { # islanders use an existing color
            $NodeColor{$_} = head 1, sort values %NodeColor for @{$OneMany{''}};
        }
    }
    %NodeColor
}

my @DATA = (
    [ [1,2],[2,3],[3,1],[4,undef],[5,undef],[6,undef] ],
    [ [1,6],[1,7],[1,8],[2,5],[2,7],[2,8],[3,5],[3,6],[3,8],[4,5],[4,6],[4,7] ],
    [ [1,4],[1,6],[1,8],[3,2],[3,6],[3,8],[5,2],[5,4],[5,8],[7,2],[7,4],[7,6] ],
    [ [1,6],[7,1],[8,1],[5,2],[2,7],[2,8],[3,5],[6,3],[3,8],[4,5],[4,6],[4,7] ]
);

for my $d (@DATA) {
    my %result = GraphNodeColor @$d;

    my($graph,$colors);
    $graph  .= '(' . join(' ', @$_) . '), ' for @$d;
    $colors .= ' ' . $result{$$_[0]} . '-' . ($result{$$_[1]} // '') . '   ' for @$d;

    say 'Graph  : ' . $graph =~ s/,\s*$//r;
    say 'Colors : ' . $colors;
    say 'Nodes  : ' . keys %result;
    say 'Edges  : ' . @$d;
    say 'Unique : ' . uniq values %result;
    say '';
}
Output:
Graph  : (1 2), (2 3), (3 1), (4 ), (5 ), (6 )
Colors :  0-1    1-2    2-0    0-    0-    0-
Nodes  : 6
Edges  : 6
Unique : 3

Graph  : (1 6), (1 7), (1 8), (2 5), (2 7), (2 8), (3 5), (3 6), (3 8), (4 5), (4 6), (4 7)
Colors :  0-1    0-1    0-1    0-1    0-1    0-1    0-1    0-1    0-1    0-1    0-1    0-1
Nodes  : 8
Edges  : 12
Unique : 2

Graph  : (1 4), (1 6), (1 8), (3 2), (3 6), (3 8), (5 2), (5 4), (5 8), (7 2), (7 4), (7 6)
Colors :  0-1    0-2    0-3    1-0    1-2    1-3    2-0    2-1    2-3    3-0    3-1    3-2
Nodes  : 8
Edges  : 12
Unique : 4

Graph  : (1 6), (7 1), (8 1), (5 2), (2 7), (2 8), (3 5), (6 3), (3 8), (4 5), (4 6), (4 7)
Colors :  0-1    1-0    1-0    1-0    0-1    0-1    0-1    1-0    0-1    0-1    0-1    0-1
Nodes  : 8
Edges  : 12
Unique : 2

PhixEdit

Exhaustive search, trims search space to < best so far, newused improves on unique().
Many more examples/testing would be needed before I would trust this the tiniest bit.
NB: As per talk page, when writing this I did not remotely imagine it might be used on over 400,000 nodes with over 3 million links...

-- demo\rosetta\Graph_colouring.exw
with javascript_semantics
constant tests = split("""
0-1 1-2 2-0 3
1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
""","\n",true)

function colour(sequence nodes, links, colours, soln, integer best, next, used=0)
-- fill/try each colours[next], recursing as rqd and saving any improvements.
-- nodes/links are read-only here, colours is the main workspace, soln/best are
-- the results, next is 1..length(nodes), and used is length(unique(colours)).
-- On really big graphs I might consider making nodes..best static, esp colours,
-- in which case you will probably also want a "colours[next] = 0" reset below.
    integer c = 1
    colours = deep_copy(colours)
    while c<best do
        bool avail = true
        for i=1 to length(links[next]) do
            if colours[links[next][i]]==c then
                avail = false
                exit
            end if
        end for
        if avail then
            colours[next] = c
            integer newused = used + (find(c,colours)==next)
            if next<length(nodes) then
                {best,soln} = colour(nodes,links,colours,soln,best,next+1,newused)
            elsif newused<best then
                {best,soln} = {newused,deep_copy(colours)}
            end if
        end if
        c += 1
    end while
    return {best,soln}
end function    

function add_node(sequence nodes, links, string n)
    integer rdx = find(n,nodes)
    if rdx=0 then
        nodes = append(nodes,n)
        links = append(links,{})
        rdx = length(nodes)
    end if
    return {nodes, links, rdx}
end function

for t=1 to length(tests) do
    string tt = tests[t]
    sequence lt = split(tt," "),
             nodes = {},
             links = {}
    integer linkcount = 0, left, right
    for l=1 to length(lt) do
        sequence ll = split(lt[l],"-")
        {nodes, links, left} = add_node(deep_copy(nodes),deep_copy(links),ll[1])
        if length(ll)=2 then
            {nodes, links, right} = add_node(deep_copy(nodes),deep_copy(links),ll[2])
            links[left] = deep_copy(links[left])&right
            links[right] = deep_copy(links[right])&left
            linkcount += 1
        end if
    end for
    integer ln = length(nodes)
    printf(1,"test%d: %d nodes, %d edges, ",{t,ln,linkcount})
    sequence colours = repeat(0,ln),
             soln = tagset(ln) -- fallback solution
    integer next = 1, best = ln
    printf(1,"%d colours:%v\n",colour(nodes,links,colours,soln,best,next))
end for
Output:
test1: 4 nodes, 3 edges, 3 colours:{1,2,3,1}
test2: 8 nodes, 12 edges, 2 colours:{1,2,2,2,1,2,1,1}
test3: 8 nodes, 12 edges, 2 colours:{1,2,2,2,1,2,1,1}
test4: 8 nodes, 12 edges, 2 colours:{1,2,2,2,2,1,1,1}

PythonEdit

import re
from collections import defaultdict
from itertools import count


connection_re = r"""
    (?: (?P<N1>\d+) - (?P<N2>\d+) | (?P<N>\d+) (?!\s*-))
    """

class Graph:

    def __init__(self, name, connections):
        self.name = name
        self.connections = connections
        g = self.graph = defaultdict(list)  # maps vertex to direct connections

        matches = re.finditer(connection_re, connections,
                              re.MULTILINE | re.VERBOSE)
        for match in matches:
            n1, n2, n = match.groups()
            if n:
                g[n] += []
            else:
                g[n1].append(n2)    # Each the neighbour of the other
                g[n2].append(n1)

    def greedy_colour(self, order=None):
        "Greedy colourisation algo."
        if order is None:
            order = self.graph      # Choose something
        colour = self.colour = {}
        neighbours = self.graph
        for node in order:
            used_neighbour_colours = (colour[nbr] for nbr in neighbours[node]
                                      if nbr in colour)
            colour[node] = first_avail_int(used_neighbour_colours)
        self.pp_colours()
        return colour

    def pp_colours(self):
        print(f"\n{self.name}")
        c = self.colour
        e = canonical_edges = set()
        for n1, neighbours in sorted(self.graph.items()):
            if neighbours:
                for n2 in neighbours:
                    edge = tuple(sorted([n1, n2]))
                    if edge not in canonical_edges:
                        print(f"       {n1}-{n2}: Colour: {c[n1]}, {c[n2]}")
                        canonical_edges.add(edge)
            else:
                print(f"         {n1}: Colour: {c[n1]}")
        lc = len(set(c.values()))
        print(f"    #Nodes: {len(c)}\n    #Edges: {len(e)}\n  #Colours: {lc}")


def first_avail_int(data):
    "return lowest int 0... not in data"
    d = set(data)
    for i in count():
        if i not in d:
            return i


if __name__ == '__main__':
    for name, connections in [
            ('Ex1', "0-1 1-2 2-0 3"),
            ('Ex2', "1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7"),
            ('Ex3', "1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6"),
            ('Ex4', "1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"),
            ]:
        g = Graph(name, connections)
        g.greedy_colour()
Output:
Ex1
       0-1: Colour: 0, 1
       0-2: Colour: 0, 2
       1-2: Colour: 1, 2
         3: Colour: 0
    #Nodes: 4
    #Edges: 3
  #Colours: 3

Ex2
       1-6: Colour: 0, 1
       1-7: Colour: 0, 1
       1-8: Colour: 0, 1
       2-5: Colour: 0, 1
       2-7: Colour: 0, 1
       2-8: Colour: 0, 1
       3-5: Colour: 0, 1
       3-6: Colour: 0, 1
       3-8: Colour: 0, 1
       4-5: Colour: 0, 1
       4-6: Colour: 0, 1
       4-7: Colour: 0, 1
    #Nodes: 8
    #Edges: 12
  #Colours: 2

Ex3
       1-4: Colour: 0, 1
       1-6: Colour: 0, 1
       1-8: Colour: 0, 1
       2-3: Colour: 1, 0
       2-5: Colour: 1, 0
       2-7: Colour: 1, 0
       3-6: Colour: 0, 1
       3-8: Colour: 0, 1
       4-5: Colour: 1, 0
       4-7: Colour: 1, 0
       5-8: Colour: 0, 1
       6-7: Colour: 1, 0
    #Nodes: 8
    #Edges: 12
  #Colours: 2

Ex4
       1-6: Colour: 0, 1
       1-7: Colour: 0, 1
       1-8: Colour: 0, 1
       2-5: Colour: 2, 0
       2-7: Colour: 2, 1
       2-8: Colour: 2, 1
       3-5: Colour: 2, 0
       3-6: Colour: 2, 1
       3-8: Colour: 2, 1
       4-5: Colour: 2, 0
       4-6: Colour: 2, 1
       4-7: Colour: 2, 1
    #Nodes: 8
    #Edges: 12
  #Colours: 3

Python dicts preserve insertion order and Ex2/Ex3 edges are traced in a similar way which could be the cause of exactly the same colours used for Ex2 and Ex3. The wp article must use an earlier version of Python/different ordering of edge definitions.

Ex4 changes the order of nodes enough to affect the number of colours used.

RakuEdit

(formerly Perl 6)

sub GraphNodeColor(@RAW) {
   my %OneMany = my %NodeColor;
   for @RAW { %OneMany{$_[0]}.push: $_[1] ; %OneMany{$_[1]}.push: $_[0] }
   my @ColorPool = "0", "1" … ^+%OneMany.elems; # as string
   my %NodePool  = %OneMany.BagHash; # this DWIM is nice
   if %OneMany<NaN>:exists { %NodePool{$_}:delete for %OneMany<NaN>, NaN } # pending
   while %NodePool.Bool {
      my $color = @ColorPool.shift;
      my %TempPool = %NodePool;
      while (my \n = %TempPool.keys.sort.first) {
         %NodeColor{n} = $color;
         %TempPool{n}:delete;
         %TempPool{$_}:delete for @(%OneMany{n}) ; # skip neighbors as well
         %NodePool{n}:delete;
      }
   }
   if %OneMany<NaN>:exists { # islanders use an existing color
      %NodeColor{$_} = %NodeColor.values.sort.first for @(%OneMany<NaN>)
   }
   return %NodeColor
}

my \DATA = [
   [<0 1>,<1 2>,<2 0>,<3 NaN>,<4 NaN>,<5 NaN>],
   [<1 6>,<1 7>,<1 8>,<2 5>,<2 7>,<2 8>,<3 5>,<3 6>,<3 8>,<4 5>,<4 6>,<4 7>],
   [<1 4>,<1 6>,<1 8>,<3 2>,<3 6>,<3 8>,<5 2>,<5 4>,<5 8>,<7 2>,<7 4>,<7 6>],
   [<1 6>,<7 1>,<8 1>,<5 2>,<2 7>,<2 8>,<3 5>,<6 3>,<3 8>,<4 5>,<4 6>,<4 7>],
];

for DATA {
   say "DATA   : ", $_;
   say "Result : ";
   my %out = GraphNodeColor $_;
   say "$_[0]-$_[1]:\t Color %out{$_[0]} ",$_[1].isNaN??''!!%out{$_[1]} for @$_;
   say "Nodes  : ", %out.keys.elems;
   say "Edges  : ", $_.elems;
   say "Colors : ", %out.values.Set.elems;
}
Output:
DATA   : [(0 1) (1 2) (2 0) (3 NaN) (4 NaN) (5 NaN)]
Result :
0-1:     Color 0 1
1-2:     Color 1 2
2-0:     Color 2 0
3-NaN:   Color 0
4-NaN:   Color 0
5-NaN:   Color 0
Nodes  : 6
Edges  : 6
Colors : 3
DATA   : [(1 6) (1 7) (1 8) (2 5) (2 7) (2 8) (3 5) (3 6) (3 8) (4 5) (4 6) (4 7)]
Result :
1-6:     Color 0 1
1-7:     Color 0 1
1-8:     Color 0 1
2-5:     Color 0 1
2-7:     Color 0 1
2-8:     Color 0 1
3-5:     Color 0 1
3-6:     Color 0 1
3-8:     Color 0 1
4-5:     Color 0 1
4-6:     Color 0 1
4-7:     Color 0 1
Nodes  : 8
Edges  : 12
Colors : 2
DATA   : [(1 4) (1 6) (1 8) (3 2) (3 6) (3 8) (5 2) (5 4) (5 8) (7 2) (7 4) (7 6)]
Result :
1-4:     Color 0 1
1-6:     Color 0 2
1-8:     Color 0 3
3-2:     Color 1 0
3-6:     Color 1 2
3-8:     Color 1 3
5-2:     Color 2 0
5-4:     Color 2 1
5-8:     Color 2 3
7-2:     Color 3 0
7-4:     Color 3 1
7-6:     Color 3 2
Nodes  : 8
Edges  : 12
Colors : 4
DATA   : [(1 6) (7 1) (8 1) (5 2) (2 7) (2 8) (3 5) (6 3) (3 8) (4 5) (4 6) (4 7)]
Result :
1-6:     Color 0 1
7-1:     Color 1 0
8-1:     Color 1 0
5-2:     Color 1 0
2-7:     Color 0 1
2-8:     Color 0 1
3-5:     Color 0 1
6-3:     Color 1 0
3-8:     Color 0 1
4-5:     Color 0 1
4-6:     Color 0 1
4-7:     Color 0 1
Nodes  : 8
Edges  : 12
Colors : 2

WrenEdit

Translation of: Go
Library: Wren-dynamic
Library: Wren-sort
Library: Wren-fmt
import "/dynamic" for Struct
import "/sort" for Sort
import "/fmt" for Fmt

// (n)umber of node and its (v)alence i.e. number of neighbors
var NodeVal = Struct.create("NodeVal", ["n", "v"])

class Graph {
    construct new(nn, st) {
        _nn  = nn                       // number of nodes
        _st  = st                       // node numbering starts from
        _nbr = List.filled(nn, null)    // neighbor list for each node
        for (i in 0...nn) _nbr[i] = []
    }

    nn { _nn }
    st { _st }

    // Note that this creates a single 'virtual' edge for an isolated node.
    addEdge(n1, n2) {
        // adjust to starting node number
        n1 = n1 - _st
        n2 = n2 - _st
        _nbr[n1].add(n2)
        if (n1 != n2) _nbr[n2].add(n1)
    }

    // Uses 'greedy' algorithm.
    greedyColoring {
        // create a list with a color for each node
        var cols = List.filled(_nn, -1) // -1 denotes no color assigned
        cols[0] = 0  // first node assigned color 0
        // create a bool list to keep track of which colors are available
        var available = List.filled(_nn, false)
        // assign colors to all nodes after the first
        for (i in 1..._nn) {
            // iterate through neighbors and mark their colors as available
            for (j in _nbr[i]) {
                if (cols[j] != -1) available[cols[j]] = true
            }
            // find the first available color
            var c = available.indexOf(false)
            cols[i] = c  // assign it to the current node
            // reset the neighbors' colors to unavailable
            // before the next iteration
            for (j in _nbr[i]) {
                if (cols[j] != -1) available[cols[j]] = false
            }
        }
        return cols
    }

    // Uses Welsh-Powell algorithm.
    wpColoring {
        // create NodeVal for each node
        var nvs = List.filled(_nn, null)
        for (i in 0..._nn) {
            var v = _nbr[i].count
            if (v == 1 && _nbr[i][0] == i) {  // isolated node
                v = 0
            }
            nvs[i] = NodeVal.new(i, v)
        }
        // sort the NodeVals in descending order by valence
        var cmp = Fn.new { |nv1, nv2| (nv2.v - nv1.v).sign }
        Sort.insertion(nvs, cmp) // stable sort

        // create colors list with entries for each node
        var cols = List.filled(_nn, -1)  // set all nodes to no color (-1) initially
        var currCol = 0 // start with color 0
        for (f in 0..._nn-1) {
            var h = nvs[f].n
            if (cols[h] != -1) {  // already assigned a color
                continue
            }
            cols[h] = currCol
            // assign same color to all subsequent uncolored nodes which are
            // not connected to a previous colored one
            var i = f + 1
            while (i < _nn) {
                var outer = false
                var j = nvs[i].n
                if (cols[j] != -1) {  // already colored
                    i = i + 1
                    continue
                }
                var k = f
                while (k < i) {
                    var l = nvs[k].n
                    if (cols[l] == -1) {  // not yet colored
                        k = k + 1
                        continue
                    }
                    if (_nbr[j].contains(l)) {
                        outer = true
                        break  // node j is connected to an earlier colored node
                    }
                    k = k + 1
                }
                if (!outer) cols[j] = currCol
                i = i + 1
            }
            currCol = currCol + 1
        }
        return cols
    }
}

var fns = [Fn.new { |g| g.greedyColoring }, Fn.new { |g| g.wpColoring }]
var titles = ["'Greedy'", "Welsh-Powell"]
var nns = [4, 8, 8, 8]
var starts = [0, 1, 1, 1]
var edges1 = [[0, 1], [1, 2], [2, 0], [3, 3]]
var edges2 = [[1, 6], [1, 7], [1, 8], [2, 5], [2, 7], [2, 8],
    [3, 5], [3, 6], [3, 8], [4, 5], [4, 6], [4, 7]]
var edges3 = [[1, 4], [1, 6], [1, 8], [3, 2], [3, 6], [3, 8],
    [5, 2], [5, 4], [5, 8], [7, 2], [7, 4], [7, 6]]
var edges4 = [[1, 6], [7, 1], [8, 1], [5, 2], [2, 7], [2, 8],
    [3, 5], [6, 3], [3, 8], [4, 5], [4, 6], [4, 7]]
var j = 0
for (fn in fns) {
    System.print("Using the %(titles[j]) algorithm:\n")
    var i = 0
    for (edges in [edges1, edges2, edges3, edges4]) {
        System.print("  Example %(i+1)")
        var g = Graph.new(nns[i], starts[i])
        for (e in edges) g.addEdge(e[0], e[1])
        var cols = fn.call(g)
        var ecount = 0  // counts edges
        for (e in edges) {
            if (e[0] != e[1]) {
                Fmt.print("    Edge  $d-$d -> Color $d, $d", e[0], e[1],
                    cols[e[0]-g.st], cols[e[1]-g.st])
                ecount = ecount + 1
            } else {
                Fmt.print("    Node  $d   -> Color $d\n", e[0], cols[e[0]-g.st])
            }
        }
        var maxCol = 0  // maximum color number used
        for (col in cols) {
            if (col > maxCol) maxCol = col
        }
        System.print("    Number of nodes  : %(nns[i])")
        System.print("    Number of edges  : %(ecount)")
        System.print("    Number of colors : %(maxCol+1)")
        System.print()
        i = i + 1
    }
    j = j + 1
}
Output:
Using the 'Greedy' algorithm:

  Example 1
    Edge  0-1 -> Color 0, 1
    Edge  1-2 -> Color 1, 2
    Edge  2-0 -> Color 2, 0
    Node  3   -> Color 0

    Number of nodes  : 4
    Number of edges  : 3
    Number of colors : 3

  Example 2
    Edge  1-6 -> Color 0, 1
    Edge  1-7 -> Color 0, 1
    Edge  1-8 -> Color 0, 1
    Edge  2-5 -> Color 0, 1
    Edge  2-7 -> Color 0, 1
    Edge  2-8 -> Color 0, 1
    Edge  3-5 -> Color 0, 1
    Edge  3-6 -> Color 0, 1
    Edge  3-8 -> Color 0, 1
    Edge  4-5 -> Color 0, 1
    Edge  4-6 -> Color 0, 1
    Edge  4-7 -> Color 0, 1
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 2

  Example 3
    Edge  1-4 -> Color 0, 1
    Edge  1-6 -> Color 0, 2
    Edge  1-8 -> Color 0, 3
    Edge  3-2 -> Color 1, 0
    Edge  3-6 -> Color 1, 2
    Edge  3-8 -> Color 1, 3
    Edge  5-2 -> Color 2, 0
    Edge  5-4 -> Color 2, 1
    Edge  5-8 -> Color 2, 3
    Edge  7-2 -> Color 3, 0
    Edge  7-4 -> Color 3, 1
    Edge  7-6 -> Color 3, 2
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 4

  Example 4
    Edge  1-6 -> Color 0, 1
    Edge  7-1 -> Color 1, 0
    Edge  8-1 -> Color 1, 0
    Edge  5-2 -> Color 1, 0
    Edge  2-7 -> Color 0, 1
    Edge  2-8 -> Color 0, 1
    Edge  3-5 -> Color 0, 1
    Edge  6-3 -> Color 1, 0
    Edge  3-8 -> Color 0, 1
    Edge  4-5 -> Color 0, 1
    Edge  4-6 -> Color 0, 1
    Edge  4-7 -> Color 0, 1
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 2

Using the Welsh-Powell algorithm:

  Example 1
    Edge  0-1 -> Color 0, 1
    Edge  1-2 -> Color 1, 2
    Edge  2-0 -> Color 2, 0
    Node  3   -> Color 0

    Number of nodes  : 4
    Number of edges  : 3
    Number of colors : 3

  Example 2
    Edge  1-6 -> Color 0, 1
    Edge  1-7 -> Color 0, 1
    Edge  1-8 -> Color 0, 1
    Edge  2-5 -> Color 0, 1
    Edge  2-7 -> Color 0, 1
    Edge  2-8 -> Color 0, 1
    Edge  3-5 -> Color 0, 1
    Edge  3-6 -> Color 0, 1
    Edge  3-8 -> Color 0, 1
    Edge  4-5 -> Color 0, 1
    Edge  4-6 -> Color 0, 1
    Edge  4-7 -> Color 0, 1
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 2

  Example 3
    Edge  1-4 -> Color 0, 1
    Edge  1-6 -> Color 0, 2
    Edge  1-8 -> Color 0, 3
    Edge  3-2 -> Color 1, 0
    Edge  3-6 -> Color 1, 2
    Edge  3-8 -> Color 1, 3
    Edge  5-2 -> Color 2, 0
    Edge  5-4 -> Color 2, 1
    Edge  5-8 -> Color 2, 3
    Edge  7-2 -> Color 3, 0
    Edge  7-4 -> Color 3, 1
    Edge  7-6 -> Color 3, 2
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 4

  Example 4
    Edge  1-6 -> Color 0, 1
    Edge  7-1 -> Color 1, 0
    Edge  8-1 -> Color 1, 0
    Edge  5-2 -> Color 1, 0
    Edge  2-7 -> Color 0, 1
    Edge  2-8 -> Color 0, 1
    Edge  3-5 -> Color 0, 1
    Edge  6-3 -> Color 1, 0
    Edge  3-8 -> Color 0, 1
    Edge  4-5 -> Color 0, 1
    Edge  4-6 -> Color 0, 1
    Edge  4-7 -> Color 0, 1
    Number of nodes  : 8
    Number of edges  : 12
    Number of colors : 2

zklEdit

fcn colorGraph(nodeStr){	// "0-1 1-2 2-0 3"
   numEdges,graph := 0,Dictionary();  // ( 0:(1,2), 1:L(0,2), 2:(1,0), 3:() )
   foreach n in (nodeStr.split(" ")){ // parse string to graph
      n=n - " ";
      if(n.holds("-")){
	 a,b := n.split("-");	// keep as string
	 graph.appendV(a,b); graph.appendV(b,a); 
	 numEdges+=1;
      }
      else graph[n]=T;		// island
   }
   colors,colorPool := Dictionary(), ["A".."Z"].walk();
   graph.pump(Void,'wrap([(node,nbrs)]){  // ( "1",(0,2), "3",() )
      clrs:=colorPool.copy();	// all colors are available, then remove neighbours
      foreach i in (nbrs){ clrs.remove(colors.find(i)) }  // if nbr has color, color not available
      colors[node] = clrs[0];	// first available remaining color
   });
   return(graph,colors,numEdges)
}
fcn printColoredGraph(graphStr){
   graph,colors,numEdges := colorGraph(graphStr);
   nodes:=graph.keys.sort();
   println("Graph: ",graphStr);
   println("Node/color: ",
       nodes.pump(List,'wrap(v){ String(v,"/",colors[v]) }).concat(", "));
   println("Node : neighbours --> colors:");
   foreach node in (nodes){
      ns:=graph[node];
      println(node," : ",ns.concat(" "),"  -->  ",
              colors[node]," : ",ns.apply(colors.get).concat(" "));
   }
   println("Number nodes:  ",nodes.len());
   println("Number edges:  ",numEdges);
   println("Number colors: ",
       colors.values.pump(Dictionary().add.fp1(Void)).len());	// create set, count
   println();
}
graphs:=T(
   "0-1 1-2 2-0 3", 
   "1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7", 
   "1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6",
   "1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7"
);
graphs.apply2(printColoredGraph);
Output:
Graph: 0-1 1-2 2-0 3
Node/color: 0/A, 1/B, 2/C, 3/A
Node : neighbours --> colors:
0 : 1 2  -->  A : B C
1 : 0 2  -->  B : A C
2 : 1 0  -->  C : B A
3 :   -->  A : 
Number nodes:  4
Number edges:  3
Number colors: 3

Graph: 1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7
Node/color: 1/A, 2/A, 3/A, 4/A, 5/B, 6/B, 7/B, 8/B
Node : neighbours --> colors:
1 : 6 7 8  -->  A : B B B
2 : 5 7 8  -->  A : B B B
3 : 5 6 8  -->  A : B B B
4 : 5 6 7  -->  A : B B B
5 : 2 3 4  -->  B : A A A
6 : 1 3 4  -->  B : A A A
7 : 1 2 4  -->  B : A A A
8 : 1 2 3  -->  B : A A A
Number nodes:  8
Number edges:  12
Number colors: 2

Graph: 1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6
Node/color: 1/A, 2/A, 3/B, 4/B, 5/C, 6/C, 7/D, 8/D
Node : neighbours --> colors:
1 : 4 6 8  -->  A : B C D
2 : 3 5 7  -->  A : B C D
3 : 2 6 8  -->  B : A C D
4 : 1 5 7  -->  B : A C D
5 : 2 4 8  -->  C : A B D
6 : 1 3 7  -->  C : A B D
7 : 2 4 6  -->  D : A B C
8 : 1 3 5  -->  D : A B C
Number nodes:  8
Number edges:  12
Number colors: 4

Graph: 1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7
Node/color: 1/A, 2/A, 3/A, 4/A, 5/B, 6/B, 7/B, 8/B
Node : neighbours --> colors:
1 : 6 7 8  -->  A : B B B
2 : 5 7 8  -->  A : B B B
3 : 5 6 8  -->  A : B B B
4 : 5 6 7  -->  A : B B B
5 : 2 3 4  -->  B : A A A
6 : 1 3 4  -->  B : A A A
7 : 1 2 4  -->  B : A A A
8 : 1 2 3  -->  B : A A A
Number nodes:  8
Number edges:  12
Number colors: 2