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

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.disc.2012.08.007 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2021054513 / rank
 
Normal rank

Revision as of 22:13, 19 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

    Identifiers