Inflations of anti-cycles and Hadwiger’s Conjecture
Anders Sune Pedersen, Michael D. Plummer, Bjarne Toft · Journal of Combinatorics · 2016
Let G be any graph.An inflation of a graph G is obtained from G first by replacing each of its vertices with either the empty set or a complete graph, and then whenever two vertices x and y are adjacent in G we join each vertex of the replacement clique for x to each vertex of the replacement clique for y by an edge.Let G be any inflation of the complement of an odd cycle.It is shown that ( 1)by a short direct proof; that is to say, Hadwiger's Conjecture holds for G.We present a comprehensive survey of the area surrounding these results.