On Triangles and Minors
The code and files belows list the graphs on at most 9 (resp. 11) vertices
with minimum degree 5 (resp. 6) which do not induce a K_6 (resp. K_7) as a minor.
All the computations are been done using Sage 5.3,
Nauty 2.4r2. The list of graph is provided in Sage
format ".sobj". The following file is a modified version of the minor function in Sage.
It has been used to improve minor checking for complete graph (it uses the symetries of the complete graph)
and do not parallelize the LP part : cliqueminor1trd.spyx
Graphs of size at most 9 with minimum degree 5
Graphs of size 8 : nok6size8.sobj, nok6size8.sage
Graphs of size 9 : nok6size8.sobj, nok6size8.sage
Graphs of size at most 11 with minimum degree 6
Graphs of size 8 : nominor082425.sobj, nok7size8.sage
The others files are provided without a source file as it is just a modification of the previous one. The graphs on 11 vertices have been
splitted according to their number of edges.
Graphs of size 9 : nominor092730.sobj
Graphs of size 10 : nominor103035.sobj
Graphs of size 11 with 33 edges : nominor113333.sobj
Graphs of size 11 with 34 edges : nominor113434.sobj
Graphs of size 11 with 35 edges : nominor113535.sobj
Graphs of size 11 with 36 edges : nominor113636.sobj
Graphs of size 11 with 37 edges : nominor113737.sobj
Graphs of size 11 with 38 edges : nominor113838.sobj
Graphs of size 11 with 39 edges : nominor113939.sobj
Graphs of size 11 with 40 edges : nominor114040.sobj
Properties checking
The following file check if every graph have at most one vertex with each edge belonging to n triangles.
Otherwise a message is shown with the position of the graph violating this property.
findtriangles.sage
The following file add an apex to each graph and check that for every combination of subset of the original graph
of fixed size n, the graph contains a complete minor of size n + 1. If not it shows a message giving the position
of the graph in the list and the corresponding subset.
findseparator.sage