Edge Coloring Using a Constructive Proof of Vizing’s Theorem¶
Samuel Rabinowitz
August 7, 2020
Algorithm¶
Outline of Algorithm¶
- We want to $k$-color graph $H = \{V, E\}$ where $V = \{v_0, \dotsc, v_{n-1}\}$.
- We need to have a $k$-coloring of $H' = \{V', E\}$ where $V' = \{v_0, \dotsc, v_{n-2}\}$, so find this recursively. This is our first recursive call.
- We choose $v = v_{n-1}$.
- Enumerate the neighbors of $v$, $[u_i]^{deg(v) - 1}_0$.
- For each $u_i$, enumerate which edge colors are not adjacent to $u_i$. The original proof calls for us to give each $u_i$ dummy neighbor vertices until each $u_i$ has degreee $k - 1$, except one $u_i$ of degree $k$. However, we can instead remove colors from each $u_i$'s missing color list until each list has two colors, except one list has 1 color.
- Now, we can find $[X_i]^{k - 1}_0$ where $X_i$ is the set of neighbors of $v$ that are not adjacent to color $i$.
- Check if there exists an $X_i$ where $\lvert X_i \rvert = 1$. Until we find such an $X_i$, we must perform the following.
- Find $X_{min}$ where $\lvert X_{min} \rvert \le \lvert X_i \rvert$ and $X_{max}$ where $\lvert X_{max} \rvert \ge \lvert X_i \rvert$.
- Check each vertex in $X_{max}$ that is not also in $X_{min}$ until we are able to find a vertex $u$ that is at one end of a path of vertices connected only by colors $min$ and $max$ where the other end of this path is not a vertex in $X_{min}$. The proof of Vizing's Theorem included explains why we can always find such a vertex and path.
- Swap all edge colors along the path that we have found. This effectively reallocates either one or two vertices from $X_{max}$ to $X_{min}$.
- Now, we must have an $X_i$ where $\lvert X_i \rvert = 1$. The proof also explains why this is the case. We want $\lvert X_{k - 1} \rvert = 1$, so if this is not already the case, we are able to swap color $k - 1$ with another color in our graph so that we get the desired result.
- We then label the one vertex in $X_{k - 1}$ as $u$.
- We color edge $\overleftrightarrow{vu}$ color $k - 1$.
- Delete all edges in our graph of color $k - 1$, and recursively try to $(k - 1)$-color $H'' = \{V, E'\}$ where $E'$ is all the edges in $H$ that are not already colored $k - 1$. We do not need to make any copies of our data here, or delete any edges as the proof may call for, since our algorithm at all steps will ignore edges of color $\ge k$. This is our second recursive call. My goal was to get $O(n \times k)$ recursive calls. I tried culling unnecessary calls that would just recolor edges that were already colored. I also tried dynamic programing with an $n \times k$ table, but this did not work because how we color a subgraph is affected by previous coloring steps in this algorithm. That means that this algorithm makes $O(2^{n + k})$ calls, which is not good.
- Add back all $(k - 1)$ colored edges in $H$, and we have a $k$ coloring of $H$.
Other notes about the implementation¶
I implemented a set of functions for handling and drawing edge colored graphs, since I could not find any useful libraries that implemented graphs the way I wanted them to be implemented. I used an adjacency list instead of an adjacency matrix. If you enable verbose mode when running the edge coloring algorithm, it will output edge colorings of the graph that show progress through the algorithm, along with visual cues to show where in the algorithm the code is. However, due to the exponential complexity of this algorithm, verbose mode outputs a very large number of steps, even for small graphs. I also tried to make the steps a gif or video file, but there seem to be odd requirements for doing this with matplotlib that would have required me to implement a wrapper function that emulates calls to matplotlib.pyplot but does not actually plot anything. Instead, it would have to store all these calls in a list so that when I want to generate the gif later, I can recall previous graphs and re-graph them at will. I decided not to implement this since it is not really relevant to the actual project. The second code cell shows how to use my colored_graph class.
Takeaways¶
This algorithm is very impractical for large graphs. For me, creating this was more of a proof of concept than anything else. I wanted to show that I could follow the steps in a constructive proof of Vizing's Theorem and actually generate an edge coloring based on that theorem. It does not seem possible to edge color in polynomial time, and a quick Google search confirms this suspicion. Therefore, I do not even know if my algorithm is faster than brute force, but I suppose it is more interesting.
In [1]:
import numpy as np
import matplotlib.pyplot as plt
import math
import seaborn as sns
class colored_graph:
# initialization functions
# we can initialize a complete graph, give an adjacency matrix, or neither
def __init__(self, complete = None, matrix = None, verbose = False):
self.__v_list = []
self.__col_list = []
self.__colors = []
self.verbose = verbose
self.__fig = plt.Figure()
if(complete):
self.__make_complete(complete)
elif(matrix):
self.__import_matrix(matrix)
pass
# make a complete graph of degree k
def __make_complete(self, k):
for i in range(k):
v_i = []
c_i = []
for j in range(k):
if(i != j):
v_i.append(j)
c_i.append(-1)
self.__v_list.append(v_i)
self.__col_list.append(c_i)
# import an adjacency matrix
# note: we must convert the matrix into an adjaceny list
# note: I do not use this function, so I have not fully tested it
def __import_matrix(self, matrix):
assert(matrix.shape[0] == matrix.shape[1])
for i in range(matrix.shape[0]):
edges_i = []
colors_i = []
for j in range(matrix.shape[1]):
if(matrix[i][j] > 0):
list_i.append(j)
colors_i.append(-1)
self.__v_list.append(list_i)
self.__col_list.append(colors_i)
# graph utility functions
def add_vertex(self):
self.__v_list.append([])
self.__col_list.append([])
return len(self.__v_list) - 1
# check to make sure a and b are not already connected
# the graph should be undirected, but it gives
# me peace of mind to check twice here
def connect_chk(self, a, b):
if not (a in self.__v_list[b]):
self.__v_list[b].append(a)
self.__col_list[b].append(-1)
if not (b in self.__v_list[a]):
self.__v_list[a].append(b)
self.__col_list[a].append(-1)
# this may fail down the line if a and b are already connected
def connect(self, a, b):
self.__v_list[b].append(a)
self.__col_list[b].append(-1)
self.__v_list[a].append(b)
self.__col_list[a].append(-1)
# drawing functions
# when we draw the graph, we arrange the vertices into a circle
def __get_circle_coordinates(self):
n_v = len(self.__v_list)
coords = np.zeros((2, n_v))
for i in range(n_v):
coords[0, i] = math.cos(i * 2 * math.pi / n_v)
coords[1, i] = math.sin(i * 2 * math.pi / n_v)
return coords
# maps color numbers [0, k - 1] to matplotlib color
# edges that are not already colored (color -1) should be black
def __get_color(self, e_color):
if(e_color < 0):
return "k"
else:
return self.__colors[e_color]
# we typically operate on a subgraph of G, H, so this makes
# edge that are part of H solid, or dashed otherwise
# n is the number of vertices in H, and k is the number of edges
def __get_style(self, e_color, n, k, source, dest):
if(e_color < 0 or e_color >= k or source >= n or dest >= n):
return "--"
else:
return "-"
# draw colored edges between vertices
def __draw_lines(self, coords, n, k):
n_v = len(self.__v_list)
for i in range(n_v):
for j in range(len(self.__v_list[i])):
dest = self.__v_list[i][j]
e_color = self.__col_list[i][j]
plt.plot([coords[0, i], coords[0, dest]], [coords[1, i], coords[1, dest]], self.__get_style(e_color, n, k, i, dest), color = self.__get_color(e_color))
# draw graph with edge colors
# note: edges with unassigned colors or colors >= k are dashed
# note: vertices >= n are drawn with x's instead of o's
# highlight highlights vertex n - 1 red
def __draw_partial_graph(self, n, k, highlight = True):
coords = self.__get_circle_coordinates()
self.__draw_lines(coords, n, k)
plt.plot(coords[0][:n - 1], coords[1][:n - 1], "ko")
high_style = "ko"
if highlight:
high_style = "ro"
plt.plot([coords[0][n - 1]], [coords[1][n - 1]], high_style)
plt.plot(coords[0][n:], coords[1][n:], "kx")
for i in range(coords.shape[1]):
plt.annotate(str(i), coords[:,i])
plt.xlim(-2, 2)
plt.ylim(-2, 2)
plt.axis("scaled")
plt.axis("off")
plt.show()
# draw full graph
def draw_graph(self):
self.__draw_partial_graph(len(self.__v_list), self.__find_max_degree() + 1, highlight = False)
# add a text message to graph
def __draw_msg(self, msg):
plt.annotate(msg, (0, -0.75))
# Coloring Algorithm
# delta
def __find_max_degree(self):
max_deg = 0
for i in range(len(self.__v_list)):
deg_i = len(self.__v_list[i])
if(deg_i > max_deg):
max_deg = deg_i
return max_deg
# get a list of edge colors adjacent to u excluding
# edges to vertices > n - 2 or edges of color > k - 1
def __get_adj_cols(self, u, n, k):
n_adj = len(self.__v_list[u])
adj_cols = []
for i in range(n_adj):
if self.__col_list[u][i] < k and self.__v_list[u][i] < n - 1:
adj_cols.append(self.__col_list[u][i])
return adj_cols
# edge colors not present at u in subgraph
def __missing_colors(self, u, n, k):
adj_cols = self.__get_adj_cols(u, n, k)
return [col for col in range(k) if col not in adj_cols]
# note: The algorithm calls for us to generate dummy vertices
# so that each neighbor of v has degree k - 1, expect one vertex
# of degree k. The way I handle this here is that instead of
# actually generating dummy vertices, I just trim the list of
# edge colors that do not hit vertex u, which gives the same
# result. I account for this later in __follow_component and
# __follow_component_swap
def __missing_colors_w_dummies(self, u, n, k, deg):
expected_size = k - deg + 1
return self.__missing_colors(u, n, k)[:expected_size]
# x[i] is a list of vertices that
# neighbor v but lack color i
# note: we do not include neighbors of
# v where we have already colored that edge
# a color out of range(k)
def __gen_x(self, v, n, k):
x = [[] for i in range(k)]
sub = 0
u_n = len(self.__v_list[v])
valid_neighbors = 0
for ind in range(u_n):
i = self.__v_list[v][ind]
if(self.__col_list[v][ind] < k and i < n):
valid_neighbors = valid_neighbors + 1
missing = self.__missing_colors_w_dummies(i, n, k, k - sub)
for j in missing:
x[j].append(i)
sub = 1
if(valid_neighbors == 0):
return None
else:
return x
# given a path of edge colors cmin and cmax
# that start at u, find where the path ends
# note: the first edge on the path must be
# color cmin
def __follow_component(self, n, u, cmin, cmax):
if cmin in self.__col_list[u]:
i = self.__col_list[u].index(cmin)
v = self.__v_list[u][i]
if v < n:
return self.__follow_component(n, v, cmax, cmin)
else:
return u
# given a path of edge colors cmin and cmax
# that start at u, find where the path ends,
# and switch the edge colors cmin and cmax
# along the path
# note: the first edge on the path must be
# color cmin
def __follow_component_swap(self, n, u, cmin, cmax):
if cmin in self.__col_list[u]:
i = self.__col_list[u].index(cmin)
v = self.__v_list[u][i]
if v < n:
self.__col_list[u][i] = cmax
end_v = self.__follow_component_swap(n, v, cmax, cmin)
self.__col_list[v][self.__col_list[v].index(cmin)] = cmax
return end_v
else:
return u
# given len(x[cmax]) > len(x[cmin]) + 2, perform a series
# of color swaps that will transfer that will transfer either
# one or two vertices from x[cmax] to x[cmin]
def __swap_col(self, n, x, cmin, cmax):
# there is a vertex in Xcmax but not Xcmin
us = [u for u in x[cmax] if u not in x[cmin]]
v = us[0]
for u in us:
v = u
if self.__follow_component(n, u, cmin, cmax) not in x[cmin]:
break
x[cmax].remove(v)
x[cmin].append(v)
v = self.__follow_component_swap(n, v, cmin, cmax)
if v in x[cmax]:
x[cmax].remove(v)
x[cmin].append(v)
# for all colored edges in our graph, swap color a with b
# only for vertices < n
def __swap_all_col(self, n, a, b):
# n_v = len(self.__v_list)
for i in range(n):
deg_i = len(self.__v_list[i])
for j in range(deg_i):
if(self.__v_list[i][j] < n):
if(self.__col_list[i][j] == a):
self.__col_list[i][j] = b
elif(self.__col_list[i][j] == b):
self.__col_list[i][j] = a
# reset all edges of color < k between the first n vertices
def __clear_coloring(self, n, k):
for i in range(n):
deg_i = len(self.__v_list[i])
for j in range(deg_i):
if(self.__v_list[i][j] < n and self.__col_list[i][j] < k):
self.__col_list[i][j] = -1
# This is my vain attempt at dynamic programming.
# I leave it here as a memento.
# def __export_coloring(self, n, k):
# coloring = []
# for i in range(n):
# v_i = []
# deg_i = len(self.__v_list[i])
# if(self.__v_list[i][j] < n and self.__col_list[i][j] < k):
# v_i.append(self.__col_list[i][j])
# else:
# v_i.append(-1)
# coloring.append(v_i)
# self.__colorings[n - 1][k - 1] = coloring
# def __import_coloring(self, n, k):
# coloring = self.__colorings[n - 1][k - 1]
# for i in range(n):
# deg_i = len(self.__v_list[i])
# for j in range(deg_i):
# if(coloring[i][j] != -1 and self.__col_list[i][j] < k):
# self.__col_list[i][j] = coloring[i][j]
# color the edge between a and b color c,
# there must actually be an edge between
# a and b to color, or this will fail
def __color_edge(self, a, b, c):
self.__col_list[a][self.__v_list[a].index(b)] = c
self.__col_list[b][self.__v_list[b].index(a)] = c
# color the edges of H, the subgraph of the first n vertices of G, with k colors
# we ignore edges that already have colors assigned that are >= k
def __color_edges_n(self, n, k):
if(n <= 1 or k < 1):
return
self.__color_edges_n(n - 1, k)
v = n - 1
x = self.__gen_x(v, n, k)
if x:
xlens = list(map(len, x))
while 1 not in xlens:
self.__swap_col(n, x, np.argmin(xlens), np.argmax(xlens))
xlens = list(map(len, x))
i = list(map(len, x)).index(1)
u = x[i][0]
if(i != k - 1):
self.__swap_all_col(n, i, k - 1)
self.__color_edge(u, v, k - 1)
self.__clear_coloring(n, k - 1)
self.__color_edges_n(n, k - 1)
if(self.verbose):
self.__draw_msg("n: {}, k: {}".format(n, k))
self.__draw_partial_graph(n, k)
# guaranteed no more than delta + 1 colors
def color_edges(self):
n_v = len(self.__v_list)
delta = self.__find_max_degree()
# this would display the color pallete for edge coloring
# pal = sns.color_palette(n_colors = delta + 1)
# sns.palplot(pal)
# plt.show()
# self.__colors = pal.as_hex()
self.__colors = sns.color_palette(n_colors = delta + 1).as_hex()
self.__color_edges_n(n_v, delta + 1)
# makes sure no adjacent edges have the same color
def check_correct(self):
for es in self.__col_list:
if len(es) != len(set(es)):
return False
return True
Usage Example 1¶
In [2]:
g = colored_graph(complete = 4)
g.add_vertex()
g.connect(4, 0)
g.color_edges()
g.draw_graph()
if g.check_correct():
print("Edge coloring correct!")
else:
print("Edge coloring incorrect!")
Usage example 2¶
In [3]:
g_big = colored_graph(complete = 9)
g_big.color_edges()
if g_big.check_correct():
print("Edge coloring correct!")
else:
print("Edge coloring incorrect!")
