Function Repository Resource:

# VertexColoring

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]:=
 Out[1]=
 In[2]:=
 Out[2]=

Highlight vertices of the same groups:

 In[3]:=
 Out[3]=

Use the specified set of colors:

 In[4]:=
 Out[4]=
 In[5]:=
 Out[5]=

### Scope (5)

VertexColoring works with undirected graphs:

 In[6]:=
 Out[6]=
 In[7]:=
 Out[7]=
 In[8]:=
 Out[8]=

Directed graphs:

 In[9]:=
 Out[9]=
 In[10]:=
 Out[10]=
 In[11]:=
 Out[11]=

Multigraphs:

 In[12]:=
 In[13]:=
 Out[13]=
 In[14]:=
 Out[14]=

Mixed graphs:

 In[15]:=
 Out[15]=
 In[16]:=
 Out[16]=
 In[17]:=
 Out[17]=

Graphs with symbolically defined vertices:

 In[18]:=
 Out[18]=
 In[19]:=
 Out[19]=
 In[20]:=
 Out[20]=

### Options (4)

#### Method (4)

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

 In[21]:=
 Out[21]=
 In[22]:=
 Out[22]=

In this case, a 5-coloring is produced:

 In[23]:=
 Out[23]=
 In[24]:=
 Out[24]=

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

 In[25]:=
 Out[25]=

Obtain minimum coloring using Method"Optimum":

 In[26]:=
 Out[26]=
 In[27]:=
 Out[27]=
 In[28]:=
 Out[28]=

### Properties and Relations (6)

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

 In[29]:=
 Out[29]=
 In[30]:=
 Out[30]=
 In[31]:=
 Out[31]=
 In[32]:=
 Out[32]=

The Brelaz heuristic is optimal for trees:

 In[33]:=
 Out[33]=
 In[34]:=
 Out[34]=
 In[35]:=
 Out[35]=

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

 In[36]:=
 Out[36]=
 In[37]:=
 Out[37]=

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

 In[38]:=
 Out[38]=
 In[39]:=
 Out[39]=
 In[40]:=
 Out[40]=

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

 In[41]:=
 Out[41]=
 In[42]:=
 Out[42]=
 In[43]:=
 Out[43]=

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

 In[44]:=
 Out[44]=
 In[45]:=
 Out[45]=
 In[46]:=
 Out[46]=

The coloring corresponding the this chromatic number:

 In[47]:=
 Out[47]=
 In[48]:=
 Out[48]=

## Version History

• 1.0.0 – 29 June 2020