10
$\begingroup$

In version 9 and before, when the Combinatorica` package was still usable, the commands VertexColoring[g] and EdgeColoring[g] used Brelaz's heuristic to find a (not necessarily optimal) vertex/edge coloring of the graph object g.

Is there a way this can be achieved using the new commands, without manually playing with the VertexStyle/EdgeStyle parameters? To be clear, I'm interested in producing visual output, so I'm currently doing this:

Graph[PetersenGraph[],
  GraphStyle -> "BasicBlack",
  BaseStyle -> EdgeForm[{Thick, Black}],
  VertexSize -> 0.25,
  EdgeStyle -> Thick,
  VertexStyle -> {1 -> Red, 2 -> Red, 3 -> Green, 4 -> Green, 5 -> Blue, 6 -> Blue,
                  7 -> Green, 8 -> Red, 9 -> Blue, 10 -> Red}]

to obtain the following output:

colored graph

Is there any way this can be done automatically? Also, why are the edges not 100% opaque? Adding EdgeStyle-> {Thick, Opacity[1]} made no difference to the output.

$\endgroup$
7
$\begingroup$

With very minimal adjustment of the original Combinatorica code, here is an implementation of Brelaz coloring:

brelaz[g_?GraphQ] := 
     Module[{m = 0, v = VertexCount[g], cd, color, p, nc, e},
       cd = color = ConstantArray[0, v];
       While[m >= 0,
             p = Position[cd, m][[1, 1]]; 
             e = AdjacencyList[g, p];
             nc = Append[color[[e]], 0];
             color[[p]] = Min[Complement[Range[Max[nc] + 1], nc]];
             cd[[p]] = -2 v; 
             Scan[(cd[[#]]++) &, e]; 
             m = Max[cd]
       ];
       color
     ]

Test:

col = brelaz[PetersenGraph[5, 2]]
   {1, 1, 2, 2, 3, 2, 3, 1, 3, 1}

PetersenGraph[5, 2, EdgeStyle -> Gray, 
              VertexStyle -> MapIndexed[First[#2] -> ColorData[61, #1] &, col], 
              VertexSize -> Small]

Brelaz-colored Petersen graph

Compare with version 5.2:

<<DiscreteMath`Combinatorica`

VertexColoring[PetersenGraph, Algorithm -> Brelaz]
   {1, 1, 2, 2, 3, 2, 3, 1, 3, 1}

For completeness, here is the corresponding adapted edge coloring algorithm:

edgeColoring[g_?GraphQ] := Module[{c = brelaz[LineGraph[g]], e, se},
    e = Map[Sort, List @@@ EdgeList[g]];
    se = Sort[MapIndexed[Prepend[#2, #1] &, e]];
    Map[Last, Sort[Reverse[MapThread[Prepend, {se, c}], 2]]]]
$\endgroup$
  • $\begingroup$ Thank you! Any idea why the edges are slightly transparent in my example? $\endgroup$ – Luke Collins Oct 1 '17 at 22:23
  • $\begingroup$ Specify a color with an explicit alpha channel of 1, e.g. GrayLevel[1/2, 1]. $\endgroup$ – J. M. will be back soon Oct 2 '17 at 1:03
  • $\begingroup$ It's better to use _?GraphQ than _Graph. For example, Graph[1] is not a graph. You seem to be assuming that the names of the vertices are the same as their indices. This is not the case in general, even when the names are integers up to VertexCount[g] (the ordering may be different). But you can construct a graph which satisfies your assumption using IndexGraph. $\endgroup$ – Szabolcs Nov 20 '17 at 13:40
  • 1
    $\begingroup$ This agrees with Combinatorica (and the plain English description in the Combinatorica book), but it is somewhat different from what Brélaz originally described (I just looked it up). In the Combinatorica version, the "colour degree" of a vertex is the number of already coloured neighbours. In the original Brélaz version, the "colour degree" is the number of adjacent colours. That may be smaller than the number of coloured neighbours when multiple neighbours have the same colour. It's quite a bit more trouble to implement the original version. $\endgroup$ – Szabolcs Nov 21 '17 at 11:11
8
$\begingroup$

IGraph/M 0.3.93 and later include the same colouring algorithm as Combinatorica.

Needs["IGraphM`"]

IGVertexMap[
 ColorData[97],
 VertexStyle -> IGVertexColoring,
 PetersenGraph[VertexSize -> Large, GraphStyle -> "BasicBlack"]
]

enter image description here

Note that while Combinatorica claims to implement Brélaz's heuristic, the algorithm is not the same described by Brélaz here. Combinatorica chooses vertices based on the number of already coloured neighbours. Brélaz suggests choosing based on the distinct neighbouring colours ("saturation degree").

In IGraph/M 0.3.98 and later you can also use IGMinimumVertexColoring to obtain an optimal colouring.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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