Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ColorGraphEdges

Source Notebook

Color the edges of a graph so no edges incident to each other have the same color

Contributed by: Peter Cullen Burbery

ResourceFunction["ColorGraphEdges"][graph]

colors the edges of graph so no edges incident to each other have the same color.

ResourceFunction["ColorGraphEdges"][graph, colors]

uses the color function colors.

Details

The vertices are colored using ColorData[106] by default.
Finding edge colorings for graphs is an NP complete problem.

Examples

Basic Examples (2) 

Color the edges of the Petersen graph:

In[1]:=
ResourceFunction["ColorGraphEdges"][PetersenGraph[]]
Out[1]=

Use a different coloring list with ColorData:

In[2]:=
ResourceFunction["ColorGraphEdges"][PetersenGraph[], ColorData[101, "ColorList"]]
Out[2]=

Scope (1) 

Color the edges of the skeleton of the Csaszar polyhedron:

In[3]:=
ResourceFunction["ColorGraphEdges"]@ MeshConnectivityGraph[ PolyhedronData["CsaszarPolyhedron", "Polyhedron"], 0]
Out[3]=

Options (1) 

ColorGraphVertices takes the same options as Graph:

In[4]:=
ResourceFunction["ColorGraphEdges"][PetersenGraph[], ImageSize -> Large]
Out[4]=

Applications (2) 

Find edge colorings for a large random graph:

In[5]:=
ResourceFunction["ColorGraphEdges"][RandomGraph[{57, 154}], ImageSize -> Full]
Out[5]=

Color the Hoffman-Singleton graph with seven colors:

In[6]:=
ResourceFunction["ColorGraphEdges"][ GraphData["HoffmanSingletonGraph"]]
Out[6]=

Properties & Relations (2) 

Use ColorGraphVertices to color the vertices instead:

In[7]:=
ResourceFunction["ColorGraphVertices"][CompleteGraph[7]]
Out[7]=

This colors the edges:

In[8]:=
ResourceFunction["ColorGraphEdges"][CompleteGraph[7]]
Out[8]=

The number of colors needed for the edges is given by EdgeChromaticNumber:

In[9]:=
EdgeChromaticNumber[CompleteGraph[7]]
Out[9]=

Verify the count with FindEdgeColoring:

In[10]:=
Length[DeleteDuplicates[ FindEdgeColoring[CompleteGraph[7], ColorData[106, "ColorList"]]]]
Out[10]=

Possible Issues (1) 

When the function FindEdgeColoring cannot find an edge coloring, ColorGraphEdges will not color the graph:

In[11]:=
ResourceFunction["ColorGraphEdges"][ RandomGraph[BarabasiAlbertGraphDistribution[101, 4]]]
Out[11]=

Publisher

Peter Burbery

Requirements

Wolfram Language 12.3 (May 2021) or above

Version History

  • 1.1.0 – 13 July 2023
  • 1.0.0 – 16 August 2022

Related Resources

License Information