Function Repository Resource:

# FindProperColorings

Find all proper k-colorings of a specified graph

Contributed by: Daniel McDonald
 ResourceFunction["FindProperColorings"][g,k] finds all proper k-colorings of the graph g.

## Details and Options

A proper k-coloring of a graph g is a function assigning each vertex of g one of k colors such that adjacent vertices receive distinct colors.
ResourceFunction["FindProperColorings"][g,k] gives a list of all proper k-colorings of g, where each coloring is a list whose ith element is an integer from 1,,k representing the color assigned to the ith vertex in VertexList[g].

## Examples

### Basic Examples (3)

Define a graph:

 In[1]:=
 Out[1]=

Find all its proper 3-colorings:

 In[2]:=
 Out[2]=

Display the proper 3-colorings:

 In[3]:=
 Out[4]=

### Scope (3)

FindProperColorings works on disconnected graphs:

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

FindProperColorings works on directed graphs:

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

FindProperColorings works on multigraphs:

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

### Applications (4)

Define a graph:

 In[14]:=
 Out[14]=

A proper k-edge-coloring of a graph g is a function assigning each edge of g one of k colors such that incident edges receive distinct colors:

 In[15]:=

Find the proper 3-edge-colorings of the graph:

 In[16]:=
 Out[16]=

Display the proper 3-edge-colorings:

 In[17]:=
 Out[9]=

### Properties and Relations (4)

Define a graph:

 In[18]:=
 Out[18]=

The chromatic polynomial f of a graph g is a function such that f(k) counts the proper k-colorings of g. Here is the chromatic polynomial of g3:

 In[19]:=
 Out[19]=

Use the chromatic polynomial to count the proper k-colorings of g3 for 1k5:

 In[20]:=
 Out[20]=

Confirm that this matches the number of proper colorings returned by FindProperColorings:

 In[21]:=
 Out[21]=

Daniel McDonald

## Version History

• 1.0.0 – 16 October 2019