# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Give a simple undirected graph a proper edge coloring using at most one color more than necessary

Contributed by:
Daniel McDonald

ResourceFunction["VizingEdgeColoring"][ finds a proper edge coloring of the simple undirected graph |

Vizing’s theorem states that if *G* is a simple undirected graph having maximum degree Δ, then *G* has a proper (Δ+1) edge coloring. Here, a proper *k* edge coloring is a coloring of the edges of *G* from a palette of *k* colors such that no vertex is incident to two or more identically colored edges. Note that at least Δ colors are needed for a proper edge coloring of *G*, to provide enough distinct colors for edges incident to vertices of maximum degree. Combined with Vizing’s theorem, it follows that the edge chromatic number of *G*, which equals the minimum *k* such that *G* has a proper k edge coloring, is either Δ or Δ+1.

The proper edge coloring is returned in the form of an Association whose key-value pairs are edges with “color” an integer that is either Δ or Δ+1.

Define a graph and find a proper edge coloring:

In[1]:= |

Out[2]= |

Define a function for plotting a proper edge coloring:

In[3]:= |

Plot the proper edge coloring:

In[4]:= |

Out[4]= |

Find a proper edge coloring for the Petersen graph:

In[5]:= |

Out[6]= |

Plot it:

In[7]:= |

Out[7]= |

Wolfram Language 11.3 (March 2018) or above

This work is licensed under a Creative Commons Attribution 4.0 International License