Function Repository Resource:

EdgeColoring

Assign colors to edges of a graph so that no two adjacent edges have the same color

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)
 ResourceFunction["EdgeColoring"][g] gives an edge coloring of graph g.

Details and Options

ResourceFunction["EdgeColoring"][g] separates edges of g into sublists such that no group contains adjacent edges—that is, edges that share a common vertex.
ResourceFunction["EdgeColoring"][g] uses the resource function VertexColoring to find a vertex coloring of the line graph of g.
ResourceFunction["EdgeColoring"] takes the Method option with the same possible values as in VertexColoring.
For simple graphs, the result of ResourceFunction["EdgeColoring"] can be used directly in HighlightGraph.
As in the resource function VertexColoring, ResourceFunction["EdgeColoring"] uses Brelaz's heuristic, which gives a good—but not necessarily minimal—coloring.
With Method"Optimum", ResourceFunction["EdgeColoring"] attempts to find a k-coloring with the smallest possible value of k (called the edge chromatic number, or chromatic index, of the graph).
ResourceFunction["EdgeColoring"] works with undirected graphs, directed graphs, multigraphs and mixed graphs, treating directed edges as undirected ones.

Examples

Basic Examples (4)

Get a sample graph:

 In[1]:=
 Out[1]=

Group edges of a graph so that no group contains adjacent edges:

 In[2]:=
 Out[2]=

Highlight edges in the groups:

 In[3]:=
 Out[3]=

Use the specified set of colors:

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

Scope (4)

EdgeColoring works with undirected graphs:

 In[6]:=
 Out[6]=

Directed graphs:

 In[7]:=
 Out[7]=

Multigraphs:

 In[8]:=
 Out[8]=

Mixed graphs:

 In[9]:=
 Out[9]=

Options (4)

Method (4)

By default, EdgeColoring uses Brelaz's heuristic, which does not necessarily give the minimum coloring:

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

In this case, a 6-coloring is produced:

 In[12]:=
 Out[12]=

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

 In[13]:=
 Out[13]=

Obtain a minimum coloring using Method"Optimum":

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

Properties and Relations (2)

EdgeColoring returns a proper edge coloring–that is, a coloring in which no two adjacent edges share the same color:

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

Verify by inspection:

 In[21]:=
 Out[21]=

Use EdgeTaggedGraph to verify an edge coloring of a multigraph by inspection:

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

Version History

• 1.0.0 – 22 October 2020