​

​
A Wolfram Notebook on Vizing’s Theorem: From Proof to Program

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
. In this demonstration, we use the Wolfram Language to turn a proof of Vizing’s theorem into a program for giving any graph
G
a proper
(Δ+1)
-edge-coloring.
Let
G=(V,E)
be a simple undirected graph. We proceed by induction on
m
, the number of edges. If
m=0
, then the theorem trivially holds. Let
m>0
; to illustrate the proof and our program, we will set
G
as the complete graph on seven vertices.
In[1]:=
graph=CompleteGraph[7]
Out[1]=
Hence we have the following palette of “colors” to choose from...
In[2]:=
colors=Range[Max[VertexDegree[graph]]+1]
Out[2]=
{1,2,3,4,5,6,7}
... and for visualization purposes we'll associate them with the following actual hues.
In[3]:=
colorAssociation=AssociationMap[Function[color,Hue[color/Length[colors]]],colors]
Out[3]=
1
,2
,3
,4
,5
,6
,7

Suppose for each edge
xy∈E
, there exists a proper
(Δ+1)
-edge-coloring
c
of the edge-deleted subgraph
G-{xy}
of
G
. We’ll start out by working with the proper
(Δ+1)
-edge-coloring
c
of
G-{xy}
below (the other vertices are preemptively named for later convenience).
In[4]:=
partialEdges={yy[2],yy[3],yy[4],yy[5],yy[6],y[2]y[3],y[2]y[4],y[2]y[5],y[2]y[6],y[3]y[4],y[3]y[5],y[3]y[6],y[4]y[5],y[4]y[6],y[5]y[6],xy[2],xy[3],xy[4],xy[5],xy[6]};​​partialGraph=Graph[partialEdges,VertexLabels"Name",GraphLayout"CircularEmbedding"];​​partialColoring=AssociationThread[partialEdges{2,4,1,3,5,5,4,7,1,7,1,6,6,3,2,6,3,2,5,4}];​​SetProperty[partialGraph,{EdgeLabelsNormal[partialColoring],EdgeStyleNormal[Map[colorAssociation,partialColoring]]}]
Out[7]=
We say that color
α∈{1,…,Δ+1}
is missing in a vertex
s∈V
with respect to the coloring
c
if for every neighbor
t
of
s
,
α
is not the color
c(st)
assigned by
c
to the edge
st
. Note that if
c
is a proper
(Δ+1)
-edge-coloring of
G
, then every vertex has a missing color with respect to
c
, since each vertex is incident to at most
Δ
colors.
We define a fan
(y(1),…,y(k))
to be a sequence of neighbors of
x
having the following three properties. First,
y(1)=y
. Second,
c(xy(i))
is missing in
y(i-1)
with respect to
c
for all
2≤i≤k
. Third, for some color
β
missing in
y(k)
with respect to
c
, either
β
is also missing in
x
with respect to
c
, or
c(xy(j))=β
for some
1≤j<k
.
To define a fan, first associate each neighbor
z
of
x
to
c(xz)
.
In[8]:=
xNeighborColoring=AssociationMap[Function[neighbor,partialColoring[Sort[xneighbor]]],AdjacencyList[partialGraph,x]]
Out[8]=
y[2]6,y[3]3,y[4]2,y[5]5,y[6]4
Next, define a function to find a color missing at a given neighbor of
x
.
In[9]:=
missingColor[node_]:=With[{usedCols=Map[partialColoring,IncidenceList[partialGraph,node]]},FirstCase[colors,(color_/;FreeQ[usedCols,color])]]​​missingColor[y[2]]
Out[10]=
3
Then, define a function to incrementally extend the fan by finding an unused neighbor
z
of
x
such that
c(xz)
is a color missing in the previous vertex of the fan with respect to
c
. Also update the available nodes, and keep track of the color too.
In[11]:=
extendFan[{node_,availableNodes_,color_}]:=With[{nextAvailableNodes=Complement[availableNodes,{node}],nextColor=missingColor[node]},{FirstCase[nextAvailableNodes,(avNode_/;xNeighborColoring[avNode]nextColor)],nextAvailableNodes,nextColor}]
Iteratively extend the fan, starting with the vertex y, all neighbors of x available and 0 as the unused dummy color. Keep going until the fan can no longer be extended.
In[12]:=
(fanIncrements=NestWhileList[extendFan,{y,Keys[xNeighborColoring],0},Composition[Not,MissingQ,First]])//MatrixForm
Out[12]//MatrixForm=
y
{y[2],y[3],y[4],y[5],y[6]}
0
y[2]
{y[2],y[3],y[4],y[5],y[6]}
6
y[3]
{y[3],y[4],y[5],y[6]}
3
y[4]
{y[4],y[5],y[6]}
2
y[5]
{y[5],y[6]}
5
y[6]
{y[6]}
4
Missing[NotFound]
{}
7
Extract the nodes and colors of the fan, make a list of the fan edges and finally make special note of the last color
β
in the fan.
In[13]:=
({fanNodes,fanColors}=Through[{Composition[Most,First],Composition[Rest,Last]}[Transpose[fanIncrements]]])//MatrixForm​​fanEdges=Map[Function[node,Sort[xnode]],fanNodes]​​lastFanCol=Last[fanColors]
To find the Kempe chain, we iteratively apply our function until it can no longer find a new vertex to extend the path.
Here’s what our Kempe chain looks like.
We can put everything together into a single function.
We also define a function for checking if a given edge-coloring is proper.