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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
ReferenceBot (talk | contribs)
Changed an Item
 
(6 intermediate revisions by 5 users not shown)
Property / reviewed by
 
Property / reviewed by: Gabriel Semanisin / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Gabriel Semanisin / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
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
Property / Wikidata QID
 
Property / Wikidata QID: Q123242136 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5422499 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hajos' graph-coloring conjecture: Variations and counterexamples / rank
 
Normal rank
Property / cites work
 
Property / cites work: Note on the colouring of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3853641 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5837979 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3924234 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Normal hypergraphs and the perfect graph conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5528475 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a special case of Hadwiger's conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some remarks on Hajós' conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4390609 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 21:26, 5 July 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