Hadwiger's conjecture and inflations of the Petersen graph
type: Item
instance of: scholarly article
title: Hadwiger's conjecture and inflations of the Petersen graph
zbMATH Open document ID: 1296.05078
author: Anders Sune Pedersen
published in: Discrete Mathematics
publication date: 2012-11-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 05C83
zbMATH DE Number: 6108945
zbMATH Keywords: Petersen graph
zbMATH Keywords: vertex colouring
zbMATH Keywords: inflations
zbMATH Keywords: Hadwiger's conjecture
reviewed by: Gabriel Semanišin
MaRDI profile type: Publication
full work available at URL: j.disc.2012.08.007
OpenAlex ID: W2021054513
Wikidata QID: Q123242136
cites work: Q5422499
cites work: Hajos' graph-coloring conjecture: Variations and counterexamples
cites work: Note on the colouring of graphs
cites work: Q3853641
cites work: Q5837979
cites work: Q3924234
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Q5528475
cites work: On a special case of Hadwiger's conjecture
cites work: Some remarks on Hajós' conjecture
cites work: Q4390609
DOI: 10.1016/J.DISC.2012.08.007
description: scientific article; zbMATH DE number 6108945