# Part of paper:
#
# On Weak Flexibility in Planar Graph
# by
# Bernard Lidický Tomáš Masařík
# Kyle Murphy Shira Zerbib
#
#
# This is a program designed to test list coloring of graphs with flexibility
# Written by Bernard Lidicky and Kyle Murphy
# At the end of program, just add as many graphs as you want and it just tests them.
#
#
# It produces the following output:
'''
bash-3.2$ sage reducible_configurations.sage
Possible non-induced pair 1 2 in (C2)
Done with testing (C2)
Done with testing (C4)
Done with testing (C5)
Done with testing (C6)
Done with testing (C7)
Done with testing (C8)
Done with testing (C9)
Done with testing (C10)
Done with testing (C11)
Done with testing (C12)
Done with testing (C13)
Done with testing (C14)
Done with testing (C15)
Possible to fix color of 2 out of 3 veritces in (D2) FIX works for [0, 2]
Done with testing (D2)
Done with testing (D2)
Possible to fix color of 0 out of 2 veritces in (D4) FIX works for []
Precoloring ONE vertex failed for (D4)
!!!!!!!!!!! FAIL !!!!!!!!!! - note if processing (D4), this is OK (D4)
Done with testing (D4)
Possible to fix color of 3 out of 4 veritces in (D5) FIX works for [1, 2, 3]
Done with testing (D5)
Possible to fix color of 1 out of 4 veritces in (D6) FIX works for [2]
Done with testing (D6)
Possible to fix color of 1 out of 5 veritces in (D7) FIX works for [1]
Done with testing (D7)
Possible non-induced pair 2 3 in (D8)
Possible to fix color of 3 out of 5 veritces in (D8) FIX works for [0, 1, 4]
Done with testing (D8)
Done with testing (D8')
Possible non-induced pair 1 2 in (D9)
Possible to fix color of 1 out of 3 veritces in (D9) FIX works for [0]
Done with testing (D9)
Done with testing (D9')
Possible to fix color of 1 out of 4 veritces in (D10) FIX works for [1]
Done with testing (D10)
Possible non-induced pair 0 3 in (D11)
Possible non-induced pair 1 3 in (D11)
Possible to fix color of 2 out of 4 veritces in (D11) FIX works for [0, 1]
Done with testing (D11)
Possible to fix color of 3 out of 4 veritces in (D11') FIX works for [0, 1, 3]
Done with testing (D11')
Possible to fix color of 3 out of 4 veritces in (D11'') FIX works for [0, 1, 3]
Done with testing (D11'')
Possible to fix color of 4 out of 5 veritces in (D12) FIX works for [0, 1, 3, 4]
Done with testing (D12)
Possible to fix color of 4 out of 7 veritces in (D3) FIX works for [0, 1, 2, 4]
Done with testing (D3)
'''
def clearly_colorable(G,L):
# Graph with no vertices is L-colorable
return (G.order() == 0)
def clearly_not_colorable(G,L):
# Surely graph with empty list is not L-colorable
for v in G.vertices():
if L[v] <= 0: return True
return False
def simplify(G,L):
# Modifies G,L by removing obvious things.
#
# Removes vertices if
# d(v) < |L(v)|
# |L(v)|=1
#
# G graph
# L indexed by vertices, contains list sizes
try_simplify=True
while(try_simplify):
try_simplify=False
# If v has just 1 color in it's list, we must use it
for v in G.vertices():
if L[v] == 1:
for u in G.neighbors(v):
L[u] -= 1
G.delete_vertex(v)
try_simplify=True
# If degree is smaller than the size of the list, we can ignore the vertex
for v in G.vertices():
if G.degree(v) < L[v]:
G.delete_vertex(v)
try_simplify=True
# Also test for Gallai tree
# If d(v)=|L(v)| for all vertices then G is not L-colorable iff it is a Gallai tree
# First we test if d(v)=|L(v)| and if yes, we try the Gallai tree
# This is needed for some of the D configurations
for CC in G.connected_components_subgraphs():
test_gallai = True
for v in CC.vertices():
if CC.degree(v) > L[v]:
test_gallai = False
break
if test_gallai and (not CC.is_gallai_tree()):
G.delete_vertices(CC.vertices())
def is_L_choosable(G,L, verbose=False):
''' Tries if a graph G is L-colorable
'''
simplify(G,L)
if clearly_colorable(G,L):
if verbose == True:
print("Greedy coloring works")
return True
if clearly_not_colorable(G,L): return False
print ("Unknown!!!! Cannot decide if G is L-colorable right away :-( ")
return False
def create_list_sizes(G, external_neighbors, listsize):
# Returns list sizes when accounted for external neighbors
list_sizes = [listsize-external_neighbors[v] for v in G.vertices()]
return list_sizes
def make_partition_list(G,L):
# Partitions the vertices baes on their list sizes
max_list_size = max(L)
list_size_partition=[[] for i in range(max_list_size+1) ]
for v in G.vertices():
list_size_partition[L[v]].append(v)
return list_size_partition
def draw_G_with_external_neighbors(G,with_external_neighbors,name):
# Makes a nice drawing of the graph by adding external neighbors
external_neighbors=[0]*G.order()
for [v,d] in with_external_neighbors:
external_neighbors[v] += d
list_size_partition = make_partition_list(G,external_neighbors)
G = G.copy()
external_edges=dict()
external_edges["blue"]=[]
for v in G.vertices():
for i in range(external_neighbors[v]):
u = G.add_vertex()
G.add_edge(u,v)
external_edges["blue"].append([u,v])
if list_size_partition:
G.graphplot(partition=list_size_partition,edge_colors=external_edges).plot(title="{} with external".format(name)).show()
else:
G.graphplot(edge_colors=external_edges).plot(title="{} with external".format(name)).show()
def process_graph(G,with_external_neighbors,name,colors,verbose=False):
# Test L-colorability of one graph G
#
# G .. Graph
# with_external_neighbors .. a list of pairs [v,d] vertex, degree. One vertex
# can have multiple entires and they should all be summed up
# name .. name of the graph
# colors .. number of colors in the lists to begin with
#
G=G.copy() # G will be damaged during the testing
external_neighbors=[0]*G.order()
for [v,d] in with_external_neighbors:
external_neighbors[v] += d
L = create_list_sizes(G, external_neighbors, colors)
if is_L_choosable(G,L):
if verbose == True:
print(":-) The graph ",name," L-colorbale")
print("")
return True
else:
if verbose == True:
print(":-( The graph ",name," in not L-colorbale")
print("")
return False
def test_identifications(G, with_external_neighbor, forbidden_subrgaphs, name):
external_neighbors=[0]*G.order()
for [v,d] in with_external_neighbor:
external_neighbors[v] += d
for u in G.vertices():
for v in G.vertices():
if u < v and external_neighbors[u] > 0 and external_neighbors[v] > 0 and (u not in G.neighbors(v)):
Guv = copy(G)
Guv.add_edge(u,v)
contains_forbidden = False
for F in forbidden_subrgaphs:
if Guv.subgraph_search(F, induced=False) != None:
contains_forbidden = True
break
if contains_forbidden:
continue
print ("Possible non-induced pair",u,v,"in",name)
def try_everything(G, with_external_neighbor, boundary_vertices, name, C_type_configuration):
''' Testing reducibility for a graph G. Tests both (FIX) and (FORB)
Parameters
----------
-G : Graph
Graph to test
-with_external_neighbor : list of pairs of integers
List of pairs [u,d], which means vertex u has d external neighbors
-boundary_vertices: list of integers
vertices, that are not in the reduced part
-name : string
name of the graph - useful for output
-C_type_configuration: bool
True if C?? configuration, False if D?? configuration
'''
# This can be used to draw the graphs and check what was entered
#draw_G_with_external_neighbors(G,with_external_neighbors,name)
#return
# fixed since we just need 4 colors
colors = 4
# List of forbidden subgraphs
forbidden_subrgaphs =[]
F1 = graphs.CycleGraph(5)
F2 = graphs.CycleGraph(6)
F3 = graphs.CycleGraph(7)
F4 = graphs.CompleteGraph(4)
#F4 is a book, forbidden only in C configurations
F5 = Graph({0:[1,2,3,4], 1:[2,3,4]})
forbidden_subrgaphs.append(F1)
forbidden_subrgaphs.append(F2)
forbidden_subrgaphs.append(F3)
forbidden_subrgaphs.append(F4)
if C_type_configuration:
forbidden_subrgaphs.append(F5)
# Test if some edges can be identified....
test_identifications(G, with_external_neighbor, forbidden_subrgaphs, name)
# We also have K_4 as a forbidden subgraph but it will never
# appear - every vertex in a reducible configuration has at most
# k-2 neighbors outside, which is 4-2 = 2 neighbors. And for K_4,
# one needs 3 neighbors.
reducible_graph = G.copy()
reducible_graph.delete_vertices(boundary_vertices)
reducible_external_neighbors = [ [v,d] for v,d in with_external_neighbor if v not in boundary_vertices ]
for bv in boundary_vertices:
for v in G[bv]:
if v not in boundary_vertices:
reducible_external_neighbors.append([v,1])
# Test if reducible part of G is L-choosable at all
#
choosable=process_graph(reducible_graph,reducible_external_neighbors,name,colors)
if choosable == False:
print("Not colorable from lists at all for",name)
print("!!!!!!!!!!! FAIL !!!!!!!!!!",name)
print("")
return False
# Testing FIX property
#
# In D configurations, FIX can be applied only to vertices with at most one
# outside neighbor
if C_type_configuration:
max_outside_neighbors = 2
else:
max_outside_neighbors = 1
external_neighbors=[0]*G.order()
for [v,d] in reducible_external_neighbors:
external_neighbors[v] += d
fix_works_for=[]
possible_fixed_colorings = 0
for v in reducible_graph.vertices():
if external_neighbors[v] <= max_outside_neighbors:
new_external_list = reducible_external_neighbors+[[v,colors-1-external_neighbors[v]]]
precolorable = process_graph(reducible_graph,new_external_list,name+"pc"+str(v),colors)
if precolorable:
possible_fixed_colorings += 1
fix_works_for.append(v)
if possible_fixed_colorings != reducible_graph.order():
print("Possible to fix color of",possible_fixed_colorings,"out of",reducible_graph.order(),"veritces in",name,"FIX works for",fix_works_for)
if possible_fixed_colorings == 0:
print("Precoloring ONE vertex failed for",name)
print("!!!!!!!!!!! FAIL !!!!!!!!!! - note if processing (D4), this is OK",name)
print ("")
# Testing FORB property
#
# In FORB, two vertices at the same time can be part of a FORB test only if the are non-adjacent
# In all configurations but (D4), size of FORB set is 1 anyway. And in (D4), if they were adjacent,
# it would create K_4
if C_type_configuration == True:
test_only_non_adjacent = False
else:
test_only_non_adjacent = True
# Try sets of size 1 and 2
for precolore_neighbors in [1,2]:
forb_sets = Combinations(reducible_graph.vertices(), precolore_neighbors)
# print ("Forb Sets:",list(forb_sets))
for forb in forb_sets:
# In case of D configurations, Forb is only for non-adjacent vertices
if test_only_non_adjacent and len(forb)==2 and (forb[1] in G[forb[0]]):
continue
Gb = G.copy()
new_v = Gb.add_vertex()
for u in forb:
Gb.add_edge(u,new_v)
# Test for a forbidden subgraph
contains_forbidden = False
for F in forbidden_subrgaphs:
if Gb.subgraph_search(F, induced=False) != None:
contains_forbidden = True
break
if contains_forbidden:
continue
# Make the new test graph by increasing the number of external neighbors
# of vertices in FORB set by 1
new_external_list = reducible_external_neighbors+[[v,1] for v in forb]
precolorable = process_graph(reducible_graph,new_external_list,name+"pc"+str(forb),colors)
if precolorable == False:
print("Precoloring fails for neighbors",forb,"in",name)
print(Gb.edges(labels=False))
print(new_external_list)
print ("!!!!!!!!!!! FAIL !!!!!!!!!!",name)
print ("")
return False
print("Done with testing",name)
return True
###############################################################
# These are the reducible configurations
# In the diagrams, the vertices in the boundary are in parentheses
C_type_configuration=True
# |
# 0
# / \
# 1 2
# / \ / \
G = Graph([[0,1],[0,2]])
with_external_neighbors=[[0,1],[1,2],[2,2]]
try_everything(G, with_external_neighbors, [], "(C2)", C_type_configuration)
#
# \ | /
# 2--1--3
# / | \
# 0
# / \
G = Graph([[0,1],[1,2],[1,3]])
with_external_neighbors=[[0,2],[1,1],[2,2],[3,2]]
# try_everything(G, with_external_neighbors, [], "(C3)", C_type_configuration) # not used
# |
# 1
# / \
# --0---2--
G = Graph([[0,1],[1,2],[0,2]])
with_external_neighbors=[[0,1],[1,1],[2,1]]
try_everything(G, with_external_neighbors, [], "(C4)", C_type_configuration)
# \ /
# 0
#\ / \
# 2--1---3
#/ \ /
# (4)
# /|\+
#
G = Graph([[0,1],[1,2],[0,3],[1,3],[1,4],[3,4]])
with_external_neighbors=[[0,2],[1,0],[2,2],[3,0],[4,3]]
try_everything(G, with_external_neighbors, [4], "(C5)", C_type_configuration)
# \|/+
# (2)
# / \
# 0---1
# \ /
# (3)
# /|\+
#
G = Graph([[0,1],[1,2],[0,2],[0,3],[1,3]])
with_external_neighbors=[[0,0],[1,0],[2,3],[3,3]]
try_everything(G, with_external_neighbors, [2,3], "(C6)", C_type_configuration)
# \|/+
# (3)
# / \
# 0--(2)+
# \ /
# 1
# |
#
G = Graph([[0,1],[0,2],[0,3],[1,2],[2,3]])
with_external_neighbors=[[0,0],[1,1],[2,3],[3,3]]
try_everything(G, with_external_neighbors, [2,3], "(C7)", C_type_configuration)
# |
# 3
# \ / \
# 0---2-
# / \ /
# 1
# |
#
G = Graph([ [0,1],[0,2],[0,3],[1,2],[2,3] ])
with_external_neighbors=[[0,2],[1,1],[2,1],[3,1]]
try_everything(G, with_external_neighbors, [], "(C8)", C_type_configuration)
#
# \ /
# 3
# |
# 2
# / \
# -0--(4)-+
# \ /
# 1
# |
#
G = Graph([[0,1],[0,2],[2,3],[0,4],[1,4],[2,4]])
with_external_neighbors=[[0,1],[1,1],[2,0],[3,2],[4,3]]
try_everything(G, with_external_neighbors, [4], "(C9)", C_type_configuration)
# \ / |
# (6) 4
# / \ /|\
# 1---2 | 5-
# \ / \|/
# 3 0
# / \ |
#
G = Graph([[0,2],[0,4],[0,5],[1,2],[1,3],[1,6],[2,3],[2,4],[2,6],[4,5]])
with_external_neighbors=[[0,1],[1,0],[2,0],[3,2],[4,1],[5,1],[6,2]]
try_everything(G, with_external_neighbors, [6], "(C10)", C_type_configuration)
# \ / \ /
# 0 4
# / \ / \
# 1---2--3---5
# \ / \ /
# (7) (6)
# /|\+ /|\+
#
G = Graph([[0,1],[0,2],[1,2],[2,3],[3,4],[3,5],[4,5],[5,6],[3,6],[1,7],[2,7]])
with_external_neighbors=[[0,2],[1,0],[2,0],[3,0],[4,2],[5,0],[6,3],[7,3]]
try_everything(G, with_external_neighbors, [6,7], "(C11)", C_type_configuration)
# \ / |
# 0 3
# / \ /|\ /
# 1---2 |(5)
# \ / \|/ \
# (6) 4
# / \
#
G = Graph([[0,1],[0,2],[1,2],[2,3],[2,4],[3,4],[4,5],[3,5],[1,6],[2,6]])
with_external_neighbors=[[0,2],[1,0],[2,0],[3,1],[4,0],[5,3],[6,3]]
try_everything(G, with_external_neighbors, [5,6], "(C12)", C_type_configuration)
# |
# 0
#\ / \
# 2--1---3-
#/ \ /
# 4
# / \
#
G = Graph([[0,1],[1,2],[0,3],[1,3],[1,4],[3,4]])
with_external_neighbors=[[0,1],[1,0],[2,2],[3,1],[4,2]]
try_everything(G, with_external_neighbors, [], "(C13)", C_type_configuration)
# \ / |
# 0 4
# / \ / \
# 1---2--3---5-
# \ / \ /
# (7) 6
# /|\+ / \
#
G = Graph([[0,1],[0,2],[1,2],[2,3],[3,4],[3,5],[4,5],[5,6],[3,6],[1,7],[2,7]])
with_external_neighbors=[[0,2],[1,0],[2,0],[3,0],[4,1],[5,1],[6,2],[7,3]]
try_everything(G, with_external_neighbors, [7], "(C14)", C_type_configuration)
# \ / \ / \ /
# 0 3 6
# / \ /|\ / \
# 1---2 | 5---7
# \ / \|/ \ /
# (9) 4 (8)
# /|\ /|\
#
G = Graph([[0,1],[0,2],[1,2],[1,9],[2,3],[2,4],[2,9],[3,4],[3,5],[4,5],[5,6],[5,7],[5,8],[6,7],[7,8]])
with_external_neighbors=[[0,2],[1,0],[2,0],[3,2],[4,0],[5,0],[6,2],[7,0],[8,3],[9,3]]
try_everything(G, with_external_neighbors, [8,9], "(C15)", C_type_configuration)
D_type_configuration = False
# \ /
# 1
# / \
# --0---2--
G = Graph([[0,1],[1,2],[0,2]])
with_external_neighbors=[[0,1],[1,2],[2,1]]
try_everything(G, with_external_neighbors, [], "(D2)", D_type_configuration)
# |
# 1
# / \
# --0---2--
G = Graph([[0,1],[1,2],[0,2]])
with_external_neighbors=[[0,1],[1,1],[2,1]]
try_everything(G, with_external_neighbors, [], "(D2)", D_type_configuration)
# \|/+
# (2)
# / \
# 0---1
# \ /
# (3)
# /|\+
#
G = Graph([[0,1],[1,2],[0,2],[0,3],[1,3]])
with_external_neighbors=[[0,0],[1,0],[2,3],[3,3]]
try_everything(G, with_external_neighbors, [2,3], "(D4)", D_type_configuration)
# |
# 3
# \ / \
# 0---2-
# / \ /
# 1
# |
#
G = Graph([ [0,1],[0,2],[0,3],[1,2],[2,3] ])
with_external_neighbors=[[0,2],[1,1],[2,1],[3,1]]
try_everything(G, with_external_neighbors, [], "(D5)", D_type_configuration)
# \ /
# 3
# / \
# 0---2-
# \ /
# 1
# / \
#
G = Graph([ [0,1],[0,2],[0,3],[1,2],[2,3] ])
with_external_neighbors=[[0,0],[1,2],[2,1],[3,2]]
try_everything(G, with_external_neighbors, [], "(D6)", D_type_configuration)
# \ /
# 0
#\ |/ \
# 2--1---3
#/ \ /
# 4
# / \
#
G = Graph([[0,1],[1,2],[0,3],[1,3],[1,4],[3,4]])
with_external_neighbors=[[0,2],[1,1],[2,2],[3,0],[4,2]]
try_everything(G, with_external_neighbors, [], "(D7)", D_type_configuration)
# |
# 0
#\ |/ \ /
# 2--1---3
#/ \ / \
# 4
# |
#
G = Graph([[0,1],[1,2],[0,3],[1,3],[1,4],[3,4]])
with_external_neighbors=[[0,1],[1,1],[2,2],[3,2],[4,1]]
try_everything(G, with_external_neighbors, [], "(D8)", D_type_configuration)
# |
# 0
#\ |/ \ /
# 2--1---3
# | \ / \
# | 4 |
# | | |
# | |
# +--------+
#
#
G = Graph([[0,1],[1,2],[0,3],[1,3],[1,4],[3,4],[2,3]])
with_external_neighbors=[[0,1],[1,1],[2,1],[3,1],[4,1]]
try_everything(G, with_external_neighbors, [], "(D8')", D_type_configuration)
# |
# 0
# / \
# 1 2
# / \ / \
G = Graph([[0,1],[0,2]])
with_external_neighbors=[[0,1],[1,2],[2,2]]
try_everything(G, with_external_neighbors, [], "(D9)", D_type_configuration)
# |
# 0
# / \
# 1---2
# / \
G = Graph([[0,1],[0,2],[1,2]])
with_external_neighbors=[[0,1],[1,1],[2,1]]
try_everything(G, with_external_neighbors, [], "(D9')", D_type_configuration)
# \ /
# 3
# \ / \
# 0---2
# / \ /
# 1
# |
#
G = Graph([ [0,1],[0,2],[0,3],[1,2],[2,3] ])
with_external_neighbors=[[0,2],[1,1],[2,0],[3,2]]
try_everything(G, with_external_neighbors, [], "(D10)", D_type_configuration)
# |
# 1
# / \ /
# --0---2--3
# / \ \
G = Graph([[0,1],[1,2],[0,2],[2,3]])
with_external_neighbors=[[0,1],[1,1],[2,2],[3,2]]
try_everything(G, with_external_neighbors, [], "(D11)", D_type_configuration)
# |
# 1
# / \ /
# 0---2--3
# | / \ \
# | |
# +-------+
#
G = Graph([[0,1],[1,2],[0,2],[2,3],[0,3]])
with_external_neighbors=[[0,0],[1,1],[2,2],[3,1]]
try_everything(G, with_external_neighbors, [], "(D11')", D_type_configuration)
# /----\
# 1 |
# / \ /
# --0---2--3
# / \ \
G = Graph([[0,1],[1,2],[0,2],[2,3],[1,3]])
with_external_neighbors=[[0,1],[1,0],[2,2],[3,1]]
try_everything(G, with_external_neighbors, [], "(D11'')", D_type_configuration)
# | |
# 1 4
# / \ / \
# --0---2---3--
# / \
G = Graph([[0,1],[1,2],[0,2],[2,3],[2,4],[3,4]])
with_external_neighbors=[[0,1],[1,1],[2,2],[3,1],[4,1]]
try_everything(G, with_external_neighbors, [], "(D12)", D_type_configuration)
# | \ /
# 0 3
# / \ / \
# 1---2---4
# \ / \ /
# 6 5
# / \ / \
#
G = Graph([[0,1],[0,2],[1,2],[1,6],[2,6],[2,3],[2,4],[2,5],[3,4],[4,5]])
with_external_neighbors=[[0,1],[1,0],[2,0],[3,2],[4,0],[5,2],[6,2]]
try_everything(G, with_external_neighbors, [], "(D3)", D_type_configuration)