Function Repository Resource:

# EdgeChromaticNumber

Compute the smallest number of colors needed in a proper edge coloring of a graph

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)
 ResourceFunction["EdgeChromaticNumber"][g] gives the minimum number of colors necessary for proper edge coloring of the graph g.

## Details and Options

A proper edge coloring is an assignment of colors to edges of the graph such that no two adjacent edges share the same color.
The edge chromatic number is also called the chromatic index.
ResourceFunction["EdgeChromaticNumber"] works with undirected graphs, directed graphs, multigraphs and mixed graphs, treating directed edges as undirected ones.

## Examples

### Basic Examples (3)

Get a sample graph:

 In[1]:=
 Out[1]=

Compute the minimum number of colors needed to color the edges of the graph so that no two adjacent edges have the same color:

 In[2]:=
 Out[2]=

Show a proper edge coloring of the graph:

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

### Scope (4)

EdgeChromaticNumber 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]=

### Properties and Relations (6)

For named graphs, the edge chromatic numbers can be obtained using GraphData:

 In[10]:=
 Out[10]=

Compute directly:

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

The edge chromatic number of a simple graph is at least the maximum vertex degree of the graph and no more than the maximum degree plus one (Vizing's theorem):

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

The edge chromatic number is exactly the maximum vertex degree of the graph for class-1 graphs, including king graphs:

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

Bipartite graphs are class-1 graphs:

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

The edge chromatic number is 1 plus the maximum vertex degree of the graph for class-2 graphs, including Petersen graphs:

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

Vizing's theorem does not hold for multigraphs:

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

## Version History

• 1.0.0 – 22 October 2020