# Help with graphs

I am trying to find the set of (surjective) homomorphic images of the Groetzsch Graph - G. I have two ideas, but I am stuck at both. Help with either would be very much appreciated.

1.I try narrowing down the candidate homomorphic images to graphs with chromatic number at least 4 and number of vertices at most 10 in house of graphs. Then i get a graph6 file and try to check if each of those graphs is a homomorphic image of G. This doesn't work because I don't know how exactly to import the graph6 file into sage.

1. Find the independent sets of G and find all the ways I can combine them into homomorphic images. I' ve heard that this is possible, but seems like a rather daunting task for me because I am very new with sage.
edit retag close merge delete

Sort by » oldest newest most voted

If s is a graph6-string representation of some graph, you can transform it into a Sage graph as follows:

sage: s = 'Jsa@IchDIS_'       # this is the graph6 representation of the GroetzschgGraph
sage: G = Graph(s)
sage: G
Graph on 11 vertices


You can check:

sage: H = graphs.GrotzschGraph()
sage: G == H
True


To go further, you shoud provide an explicit sample of a graph6 file, so that we can understand how to load it.

Regarding your secnod point, since your graph is small, you can get the list of independent sets as follows:

• put a boolean (0 or 1) variable on each vertex
• add the constraint that for each edge, the sum of the values iof the vertices defining the edge is at most 1

You get a polytope whose integer points are the independent sets of your graph. In Sage, you can do this:

sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable(binary=True)
sage: for a,b in G.edges(labels=False):
sage: P = p.polyhedron()
sage: L = P.integral_points() ; L
((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1),
(0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0),
(0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0),
(0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1),
(0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0),
(0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0),
(0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0),
(0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1),
(0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1),
(0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0),
(0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1),
(0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0),
(0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0),
(0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0),
(0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0),
(0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0),
(0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0),
(0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1),
(0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1),
(0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0),
(0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0),
(0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0),
(0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1),
(0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0),
(0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1),
(0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0),
(0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0),
(0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0),
(0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1),
(0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0),
(0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0),
(0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1),
(0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0),
(0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0),
(0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0),
(0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1),
(0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0),
(0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1),
(0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0),
(0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0),
(0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0),
(0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0),
(0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0),
(0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0),
(0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0),
(0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0),
(0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0),
(0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0),
(0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1),
(0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0),
(0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0),
(0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1),
(0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
(0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0),
(0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
(0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0),
(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
(1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
(1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0),
(1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1),
(1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0),
(1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
(1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0),
(1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0),
(1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1),
(1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0))
sage: len(L)
103


So, you have a list of 103 independent sets.

more

I understand this and I have reached that point.

However in the first question, I can't write every single graph, I need something that aoutomatically reads all ~100 graphs that are in the graph6 file. Moreover some of the graphs sage doesn't read at all - it gives errors because of certain symbols in the string of the graph.

For the second question finding the independent sets is ok, but then I need an algorithm which contracts the independent sets into new smaller graphs, so that I find hom G.

( 2018-08-06 09:31:53 -0500 )edit