Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ChromaticNumber

Source Notebook

Compute the vertex chromatic number of a graph

Contributed by: Szabolcs Horvát and Michael Sollami

ResourceFunction["ChromaticNumber"][g]

computes the vertex chromatic number χ(g) of the simple graph g.

Details and Options

ResourceFunction["ChromaticNumber"] works on both connected and unconnected simple graphs, i.e. undirected graphs containing no self-loops or multiedges.
The chromatic number of a graph is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.
This function uses a linear programming based algorithm. It works well in general, but if you need faster performance, check out IGChromaticNumber and IGMinimumVertexColoring from the igraph interface IGraph/M.

Examples

Basic Examples (3) 

Compute chromatic numbers of simple graphs:

In[1]:=
ResourceFunction["ChromaticNumber"][PetersenGraph[]]
Out[1]=

Compute chromatic numbers of graphs:

In[2]:=
(* Evaluate this cell to get the example input *) CloudGet["https://www.wolframcloud.com/obj/f43b5f5e-0067-431b-b898-e2a03a6c415c"]
Out[2]=

Compute the vertex chromatic number of famous graphs:

In[3]:=
ResourceFunction["ChromaticNumber"] /@ Table[GraphData[{"RookComplement", {n, n}}], {n, 10}]
Out[3]=

Scope (2) 

Works on graphs in either 2D or 3D form:

In[4]:=
utility = GraphData["UtilityGraph", {"Graph", "Graph3D"}]
Out[4]=
In[5]:=
ResourceFunction["ChromaticNumber"] /@ utility
Out[5]=

Special and corner cases are handled efficiently:

In[6]:=
g = CompleteGraph[24]; Labeled[g, Text@StringTemplate["\[Chi](g) = `1`"][ ResourceFunction["ChromaticNumber"]@g]]
Out[7]=

Applications (1) 

Compute on larger graphs than was possible before (with Combinatorica`):

In[8]:=
ResourceFunction["ChromaticNumber"]@\!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28}, {Null, SparseArray[ Automatic, {28, 28}, 0, {1, {{0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300, 320, 340, 360, 380, 400, 420, 440, 460, 480, 500, 520, 540, 560}, CompressedData[" 1:eJxt0UkSgyAQBVAGjRoHnGVwkxvkLDmCF8j9dwEaBSEbrHr1fzXYr+P7OQhC 6K0PrL+EZvmjKKtn3bQd64dxmhdMM6ATVi4w0bEwtEml7V40Bl1vtktzH1s3 LtUemg45y245EZnJgcGQjtkBGxfe3FAw9zafk5f5nLRd+AnNOFtSoU1LbHX7 z6Juaa89pMb60IoqzYFdOZJsiItzRd6kile02u49ZSxekZ6yxys3lk6V6gcl piGU "]}, Pattern}]}]]}, TagBox[GraphicsGroupBox[GraphicsComplexBox[CompressedData[" 1:eJwB0QEu/iFib1JlAgAAABwAAAACAAAAVP3SIQjuyD/mt5GRwKjXP4wiNCbd cOI/wEURU4upoD8r5r0fh9PpP7gz0SjJZOg/0GvwxaS25z/cYgNoUgDxPwAA AAAAAAAAevEabEhH8T/4hjqnYqTwPxYIY67ZfPI/PgzN77xO+j/KTnG1bBDt P34kFNd379Y/HrIKcTOj8j9l0q9ovcvyP/6zTLbPxug/NSOd2ir+9T8Yiniv si/WP9vqTWF/1fg/cHJJVsBWwj/GRAnZ9tHhP7DQXUEQPfw/UrOCfrt75z9k NxRN1WD3P/A5dVkpTd0/46tcmixp6z/bgFV6/PHtPxER8aGmsvs/0TPrOz9w 8j9uBgy/1ID3P3NP/8fP+fE/AAAAAAAAAABWb+onjBfqP23pwG+7/tk/oMuo iV872D+x7dbkYff3P3xbe9Dv1vA/AALd4fL+zj8eG5Pe+NT3P+1JCWXg6+U/ pE7Vh9onxT8+lH1DXVjmP9ctSDvsePo/MAC0KOOd9z/WIWCNWOf2P/QFdOBl 3PI/H6MXOWi43z/Ak/StCuLeP0ab7WM0jfU/H0AAe5VK/D/4fZlPdAL+P235 8B6poOM/6iKLraxz/T/0OFOXZ37zP7pi6Pg= "], { {Hue[0.6, 0.7, 0.5], Opacity[0.7], LineBox[CompressedData[" 1:eJwVxbeRGDEMAMAD6L0nQZOoJZXwDXz/mUab7J+f378/+H0fwff9HxAYcBAg QYEGAxYceAgQIUGGAhUadBjIkKNEhRoNWnQYMWHGghUbdhw4kXAzwSRTzDLH PAssssQyK6yyxjobbLHDLhdcc8Mtd9zzwCNPPPPCK2+888EXP/wKKZTQwggv gogiiSyKqKKJLoaYgsSWVjrpZZBRJpllkVU2OeWSJI+88imrnPIqqKiSyqqo roaaailSR131tNVOex101ElnXXTVTU+99NZHX/2MNc54E0w0yWRTTDfDTLPM Nsdc82y0yVbbbLfDTrss2W2vfS674qprrrvhpluO3HbXPR998tU33/3w0y9P fvvjX8ihhBpa6GGEGVagsMMJL9bY44wrUtzxxBtfammkmVaitNNJN73c8sgz r0x555NvfqWWXmZZhcoup9zy6qyrUt311Ftfm201aruddtvrs69OfffTb39j jjVo7HHGHW/S3OusS4cuvX323e+8+/4BVKYhfA== "]]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.021594025128350208], DiskBox[2, 0.021594025128350208], DiskBox[3, 0.021594025128350208], DiskBox[4, 0.021594025128350208], DiskBox[5, 0.021594025128350208], DiskBox[6, 0.021594025128350208], DiskBox[7, 0.021594025128350208], DiskBox[8, 0.021594025128350208], DiskBox[9, 0.021594025128350208], DiskBox[10, 0.021594025128350208], DiskBox[11, 0.021594025128350208], DiskBox[12, 0.021594025128350208], DiskBox[13, 0.021594025128350208], DiskBox[14, 0.021594025128350208], DiskBox[15, 0.021594025128350208], DiskBox[16, 0.021594025128350208], DiskBox[17, 0.021594025128350208], DiskBox[18, 0.021594025128350208], DiskBox[19, 0.021594025128350208], DiskBox[20, 0.021594025128350208], DiskBox[21, 0.021594025128350208], DiskBox[22, 0.021594025128350208], DiskBox[23, 0.021594025128350208], DiskBox[24, 0.021594025128350208], DiskBox[25, 0.021594025128350208], DiskBox[26, 0.021594025128350208], DiskBox[27, 0.021594025128350208], DiskBox[28, 0.021594025128350208]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->{"NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FormatType->TraditionalForm, FrameTicks->None, ImageSize->{96.36328125, Automatic}]\) // AbsoluteTiming
Out[8]=

Possible Issues (1) 

ChromaticNumber does not work on the output of GraphPlot:

In[9]:=
ResourceFunction["ChromaticNumber"]@GraphPlot[PetersenGraph[]]
Out[9]=

Publisher

Michael Sollami

Version History

  • 2.0.0 – 21 June 2019
  • 1.0.0 – 04 March 2019

Source Metadata

  • Citation:
    Stan Wagon and Michael Trick

License Information