Wolfram Research

Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ColorGraphEdges (1.0.0) current version: 1.1.0 »

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 colorings for graphs is an NP complete area of combinatorial research.

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

Applications (2) 

Find edge colorings for a large random graph:

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

Color the Hoffman-Singleton graph with seven colors:

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

Possible Issues (1) 

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

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

Publisher

Peter Burbery

Version History

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

Related Resources

License Information