Hadwiger's conjecture and inflations of the Petersen graph (Q1759395): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:35, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hadwiger's conjecture and inflations of the Petersen graph |
scientific article |
Statements
Hadwiger's conjecture and inflations of the Petersen graph (English)
0 references
20 November 2012
0 references
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.
0 references
Petersen graph
0 references
vertex colouring
0 references
inflations
0 references
Hadwiger's conjecture
0 references