Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ColorGraphVertices

Source Notebook

Color the vertices in a graph with no adjacent vertices sharing a color

Contributed by: Peter Cullen Burbery

ResourceFunction["ColorGraphVertices"][graph]

colors the vertices of graph with no adjacent vertices having the same color.

ResourceFunction["ColorGraphVertices"][graph, colors]

uses colors from the color list colors.

Details

Every planar graph can have colors assigned to its vertices such that no adjacent vertices have the same color with at most four colors according to the four color theorem.
The vertices are colored using ColorData[106] by default.
Deciding whether a graph can be colored with 3 or more colors is NP complete.

Examples

Basic Examples (1) 

Color the vertices of the Petersen graph:

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

Scope (2) 

Color the vertices of the Petersen graph with color list 105:

In[2]:=
ResourceFunction["ColorGraphVertices"][PetersenGraph[], ColorData[105, "ColorList"]]
Out[2]=

Color the vertices of the Petersen graph with a random sample of crayola colors:

In[3]:=
ResourceFunction["ColorGraphVertices"][PetersenGraph[], RandomSample[ColorData["Crayola", "ColorList"]]]
Out[3]=

Color the vertices of the Pappus graph:

In[4]:=
ResourceFunction["ColorGraphVertices"][GraphData["PappusGraph"]]
Out[4]=

Options (1) 

ColorGraphVertices takes the same options as Graph:

In[5]:=
ResourceFunction["ColorGraphVertices"][PetersenGraph[], ImageSize -> Large]
Out[5]=

Properties & Relations (2) 

Use ColorGraphVertices to color the vertices, or nodes of a graph or network, respectively:

In[6]:=
ResourceFunction["ColorGraphVertices"][CompleteGraph[7]]
Out[6]=

One can also color the edges:

In[7]:=
ResourceFunction["ColorGraphEdges"][CompleteGraph[7]]
Out[7]=

The number of colors needed for the vertices is given by VertexChromaticNumber:

In[8]:=
VertexChromaticNumber[PetersenGraph[]]
Out[8]=

Verify the cases with FindVertexColoring:

In[9]:=
Length[DeleteDuplicates[FindVertexColoring[PetersenGraph[]]]]
Out[9]=

Applications (3) 

Color the vertices of the skeleton of the Császár polyhedron:

In[10]:=
ResourceFunction["ColorGraphVertices"][ MeshConnectivityGraph[ PolyhedronData["CsaszarPolyhedron", "Polyhedron"], 0]]
Out[10]=

Make a large random graph and color the vertices:

In[11]:=
ResourceFunction["ColorGraphVertices"][ RandomGraph[BarabasiAlbertGraphDistribution[192, 3]], ImageSize -> Full]
Out[11]=

Make a 3D buckyball graph with colors:

In[12]:=
Graph3D[ResourceFunction["ColorGraphVertices"][BuckyballGraph[]]]
Out[12]=

Publisher

Peter Burbery

Requirements

Wolfram Language 12.3 (May 2021) or above

Version History

  • 1.1.0 – 13 July 2023
  • 1.0.0 – 23 August 2022

Related Resources

License Information