Function Repository Resource:

# ChromaticNumber

Compute the vertex chromatic number of a graph

Contributed by: Szabolcs Horvát and Michael Sollami
 ResourceFunction["ChromaticNumber"][g] computes χ(g) the vertex chromatic number of 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

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

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

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

 In[8]:=
 Out[8]=

### Possible Issues

ChromaticNumber does not work on the output of GraphPlot:

 In[9]:=
 Out[9]=