Wolfram Function Repository
Instant-use add-on functions for the Wolfram Language
Function Repository Resource:
Compute the smallest number of colors needed in a proper edge coloring of a graph
ResourceFunction["EdgeChromaticNumber"][g] gives the minimum number of colors necessary for proper edge coloring of the graph g. |
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]= | ![]() |
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]= | ![]() |
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]= | ![]() |
This work is licensed under a Creative Commons Attribution 4.0 International License