Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 VertexColoring

Source Notebook

Assign colors to vertices of a graph so that no edge connects vertices of the same color

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["VertexColoring"][g]

gives a vertex coloring of graph g.

Details and Options

ResourceFunction["VertexColoring"][g] separates vertices of g into differently colored subsets such that no subset contains adjacent vertices.
The result of ResourceFunction["VertexColoring"] can be used directly in HighlightGraph.
ResourceFunction["VertexColoring"] takes the Method option with the following possible values:
"Brelaz"Brelaz’s heuristics
"Optimum"exhaustive search for an optimum coloring
By default, ResourceFunction["VertexColoring"] uses Brelaz’s heuristic, which gives a good, but not necessarily minimal, vertex coloring.
With Method→"Optimum", ResourceFunction["VertexColoring"] attempts to find a k-coloring with the smallest possible value of k (the chromatic number of the graph).
The "Optimum" method uses the resource function BacktrackSearch.
ResourceFunction["VertexColoring"] works with undirected graphs, directed graphs, multigraphs and mixed graphs.

Examples

Basic Examples (3) 

Group vertices of a graph so that no group contains adjacent vertices:

In[1]:=
g = PetersenGraph[5, 2]
Out[1]=
In[2]:=
c = ResourceFunction["VertexColoring"][g]
Out[2]=

Highlight vertices of the same groups:

In[3]:=
HighlightGraph[g, c, VertexSize -> Large, VertexLabels -> "Name"]
Out[3]=

Use the specified set of colors:

In[4]:=
MapThread[Style, {c, {Red, Green, Blue}}]
Out[4]=
In[5]:=
HighlightGraph[g, %, VertexSize -> Large]
Out[5]=

Scope (5) 

VertexColoring works with undirected graphs:

In[6]:=
RandomGraph[{10, 30}]
Out[6]=
In[7]:=
ResourceFunction["VertexColoring"][%]
Out[7]=
In[8]:=
HighlightGraph[%%, %, VertexSize -> Medium]
Out[8]=

Directed graphs:

In[9]:=
g = Graph[{1 \[DirectedEdge] 3, 2 \[DirectedEdge] 1, 3 \[DirectedEdge] 6, 4 \[DirectedEdge] 6, 1 \[DirectedEdge] 5, 5 \[DirectedEdge] 4, 6 \[DirectedEdge] 1}, VertexLabels -> "Name"]
Out[9]=
In[10]:=
ResourceFunction["VertexColoring"][g]
Out[10]=
In[11]:=
HighlightGraph[g, %, VertexSize -> Medium]
Out[11]=

Multigraphs:

In[12]:=
g = \!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4, 5}, {{{1, 2}, {2, 3}, {2, 3}, {3, 1}, {3, 4}, {4, 5}, {5, 3}}, Null}, {EdgeStyle -> { Arrowheads[Automatic]}, FormatType -> TraditionalForm, GraphLayout -> {"Dimension" -> 2}, GridLinesStyle -> Directive[ GrayLevel[0.5, 0.4]], VertexLabels -> {"Name"}}]]}, TagBox[GraphicsGroupBox[{ {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[Automatic], ArrowBox[{{2.017540424146274, 0.00044208442469451104`}, { 2.017313638325164, 0.8021720910704471}}, 0.022753627728707843`], ArrowBox[BezierCurveBox[{{2.017313638325164, 0.8021720910704471}, {1.5786497609293124`, 0.4357165494909167}, {1.008104154360962, 0.40117133112610454`}}], 0.022753627728707843`], ArrowBox[BezierCurveBox[{{2.017313638325164, 0.8021720910704471}, {1.4467680317568175`, 0.7676268727056339}, {1.008104154360962, 0.40117133112610454`}}], 0.022753627728707843`], ArrowBox[{{1.008104154360962, 0.40117133112610454`}, { 2.017540424146274, 0.00044208442469451104`}}, 0.022753627728707843`], ArrowBox[{{1.008104154360962, 0.40117133112610454`}, {0., 0.}}, 0.022753627728707843`], ArrowBox[{{0., 0.}, {0.00022442750785334198`, 0.8026134080747779}}, 0.022753627728707843`], ArrowBox[{{0.00022442750785334198`, 0.8026134080747779}, { 1.008104154360962, 0.40117133112610454`}}, 0.022753627728707843`]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[ 0.7]}], { DiskBox[{2.017540424146274, 0.00044208442469451104}, 0.022753627728707843], InsetBox["1", Offset[{2, 2}, {2.040294051874982, 0.023195712153402354}], ImageScaled[{0, 0}], BaseStyle->"Graphics"]}, { DiskBox[{2.017313638325164, 0.8021720910704471}, 0.022753627728707843], InsetBox["2", Offset[{2, 2}, {2.040067266053872, 0.8249257187991549}], ImageScaled[{0, 0}], BaseStyle->"Graphics"]}, { DiskBox[{1.008104154360962, 0.40117133112610454}, 0.022753627728707843], InsetBox["3", Offset[{2, 2}, {1.0308577820896698, 0.4239249588548124}], ImageScaled[{0, 0}], BaseStyle->"Graphics"]}, {DiskBox[{0., 0.}, 0.022753627728707843], InsetBox["4", Offset[{2, 2}, {0.022753627728707843, 0.022753627728707843}], ImageScaled[{0, 0}], BaseStyle->"Graphics"]}, { DiskBox[{0.00022442750785334198, 0.8026134080747779}, 0.022753627728707843], InsetBox["5", Offset[{2, 2}, {0.022978055236561185, 0.8253670358034857}], ImageScaled[{0, 0}], BaseStyle->"Graphics"]}}}], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->{"NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FormatType->TraditionalForm, FrameTicks->None, GridLinesStyle->Directive[ GrayLevel[0.5, 0.4]]]\);
In[13]:=
ResourceFunction["VertexColoring"][%]
Out[13]=
In[14]:=
HighlightGraph[g, %, VertexSize -> Medium]
Out[14]=

Mixed graphs:

In[15]:=
g = Graph[{1 \[DirectedEdge] 2, 3 \[DirectedEdge] 4, 4 \[DirectedEdge] 5, 5 \[DirectedEdge] 3, 2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 1}]
Out[15]=
In[16]:=
ResourceFunction["VertexColoring"][g]
Out[16]=
In[17]:=
HighlightGraph[g, %]
Out[17]=

Graphs with symbolically defined vertices:

In[18]:=
g = VertexReplace[RandomGraph[{10, 20}], Table[i -> RandomWord[], {i, 10}], VertexLabels -> "Name"]
Out[18]=
In[19]:=
ResourceFunction["VertexColoring"][g]
Out[19]=
In[20]:=
HighlightGraph[g, %, VertexSize -> Large]
Out[20]=

Options (4) 

Method (4) 

By default, VertexColoring uses Brelaz’s heuristics, which does not necessarily give minimum coloring:

In[21]:=
g = GraphData["IcosahedralGraph"]
Out[21]=
In[22]:=
ResourceFunction["VertexColoring"][g]
Out[22]=

In this case, a 5-coloring is produced:

In[23]:=
Length[%]
Out[23]=
In[24]:=
HighlightGraph[g, %%, VertexSize -> Large]
Out[24]=

However, the minimum coloring should use only four colors, as given by the chromatic number of the graph:

In[25]:=
ResourceFunction["ChromaticNumber"][g]
Out[25]=

Obtain minimum coloring using Method→"Optimum":

In[26]:=
ResourceFunction["VertexColoring"][g, Method -> "Optimum"]
Out[26]=
In[27]:=
Length[%]
Out[27]=
In[28]:=
HighlightGraph[g, %%, VertexSize -> Large]
Out[28]=

Properties and Relations (6) 

The default Brelaz’s heuristic can produce minimum coloring for some graphs:

In[29]:=
g = GraphData["GroetzschGraph"]
Out[29]=
In[30]:=
ResourceFunction["VertexColoring"][g]
Out[30]=
In[31]:=
ResourceFunction["ChromaticNumber"][g]
Out[31]=
In[32]:=
HighlightGraph[g, %%, VertexSize -> Large]
Out[32]=

The Brelaz heuristic is optimal for trees:

In[33]:=
g = TreeGraph[ RandomInteger[#] \[UndirectedEdge] # + 1 & /@ Range[0, 30], VertexSize -> 0.4]
Out[33]=
In[34]:=
ResourceFunction["VertexColoring"][g]
Out[34]=
In[35]:=
HighlightGraph[g, %, VertexSize -> Large]
Out[35]=

The Brelaz heuristic is also optimal for complete graphs, which, by definition, are n-colorable:

In[36]:=
g = CompleteGraph[5]
Out[36]=
In[37]:=
ResourceFunction["VertexColoring"][g]
Out[37]=

Likewise, the Brelaz heuristic is optimal for complete k-partite graphs that are k-colorable:

In[38]:=
g = CompleteGraph[Range[4]]
Out[38]=
In[39]:=
ResourceFunction["VertexColoring"][g]
Out[39]=
In[40]:=
HighlightGraph[g, %, VertexSize -> Large]
Out[40]=

Grid graphs are bipartite, for the vertices can be partitioned like the squares on a chessboard:

In[41]:=
g = GridGraph[{4, 5}]
Out[41]=
In[42]:=
ResourceFunction["VertexColoring"][g]
Out[42]=
In[43]:=
HighlightGraph[g, %, VertexSize -> Medium]
Out[43]=

ChromaticPolynomial can be used to find the chromatic number of a graph:

In[44]:=
g = PetersenGraph[5, 4]
Out[44]=
In[45]:=
p[k] = ChromaticPolynomial[g, k]
Out[45]=
In[46]:=
MinValue[{k, k > 0 && p[k] > 0 }, k, Integers]
Out[46]=

The coloring corresponding the this chromatic number:

In[47]:=
ResourceFunction["VertexColoring"][g, Method -> "Optimum"]
Out[47]=
In[48]:=
HighlightGraph[g, %, VertexSize -> Large]
Out[48]=

Version History

  • 1.0.0 – 29 June 2020

License Information