Function Repository Resource:

# ChromaticNumber

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

Compute chromatic numbers of graphs:

 In[2]:=
 Out[2]=

Compute the vertex chromatic number of famous graphs:

 In[3]:=
 Out[3]=

### Scope (2)

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

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

Special and corner cases are handled efficiently:

 In[6]:=
 Out[7]=

### Applications (1)

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

 In[8]:=
 Out[8]=

### Possible Issues (1)

ChromaticNumber does not work on the output of GraphPlot:

 In[9]:=
 Out[9]=

Michael Sollami

## Version History

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