Hadwiger's conjecture and inflations of the Petersen graph (Q1759395): Difference between revisions

Hadwiger's conjecture [\textit{H. Hadwiger}, Vierteljahresschr. Naturforsch. Ges. Zürich 88, 133--142 (1943; Zbl 0061.41308)] states that every \(k\)-chromatic graph contains a complete minor of order \(k\). The paper under review deals with an inflation of graphs (an inflation of a graph \(G\) is obtained by replacing vertices in \(G\) by disjoint cliques and adding all possible edges between any pair of cliques corresponding to adjacent vertices in \(G\)). It is proved that the chromatic number of an arbitrary inflation \(F\) of the Petersen graph is equal to the chromatic number of some inflated 5-cycle contained in \(F\). This implies that Hadwiger's conjecture holds for any inflation of the Petersen graph.