The extremal function for Petersen minors

DOI10.1016/J.JCTB.2018.02.001zbMath1387.05246arXiv1508.04541OpenAlexW2232156287WikidataQ130179878 ScholiaQ130179878MaRDI QIDQ1748273

Kevin Hendrey, David R. Wood

Publication date: 9 May 2018

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We prove that every graph with $n$ vertices and at least $5n-8$ edges contains the Petersen graph as a minor, and this bound is best possible. Moreover we characterise all Petersen-minor-free graphs with at least $5n-11$ edges. It follows that every graph containing no Petersen minor is 9-colourable and has vertex arboricity at most 5. These results are also best possible.

Full work available at URL: https://arxiv.org/abs/1508.04541

zbMATH Keywords

graph minorchromatic numberextremal functionPetersen graphvertex arboricity

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average degree conditions forcing a minor
• Three-edge-colouring doublecross cubic graphs
• Graphs with no \(\bar{P}_7\)-minor
• On the vertex-arboricity of planar graphs without 7-cycles
• The edge-density for \(K_{2,t}\) minors
• \(K_{6}\) minors in large 6-connected graphs
• Forcing unbalanced complete bipartite minors
• Dense graphs have \(K_{3,t}\) minors
• Lower bound of the Hadwiger number of graphs by their average degree
• Disjoint unions of complete minors
• On \(K_{s,t}\)-minors in graphs with given average degree
• On the maximum density of graphs which have no subcontraction to \(K^ r\).
• Tutte's edge-colouring conjecture
• A splitter for graphs with no Petersen family minor
• On \(K_{s,t}\)-minors in graphs with given average degree. II
• The extremal function for complete minors
• Sachs' linkless embedding conjecture
• Excluded minors in cubic graphs
• The extremal function for noncomplete minors
• On the vertex arboricity of planar graphs of diameter two
• Cyclically five-connected cubic graphs
• The extremal function for disconnected minors
• Coloring graphs with forbidden minors
• On the vertex-arboricity of planar graphs
• On the vertex-arboricity of \(K_5\)-minor-free graphs of diameter 2
• The extremal function for \(K_{9}\) minors
• Homomorphiesätze für Graphen
• The extremal function for \(K_{8}^{-}\) minors
• Homomorphism theorems for graphs
• Über eine Eigenschaft der ebenen Komplexe
• On the critical point-arboricity graphs
• Hadwiger’s Conjecture
• A Characterization of Graphs with No Octahedron Minor
• Thomassen's Choosability Argument Revisited
• An extremal function for contractions of graphs
• Cycles of Given Size in a Dense Graph
• Contractions to k₈
• Graphs with the Circuit Cover Property
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• On triangles in ‐minor free graphs
• Forcing a sparse minor
• On the algebraic theory of graph colorings
• The Point-Arboricity of Planar Graphs
• A note on primitive skew curves
• Vertex partitions of \(K_{4,4}\)-minor free graphs

Related Items (6)

Graphs with no \(\bar{P}_7\)-minor ⋮ A lower bound on the average degree forcing a minor ⋮ Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth ⋮ Recent progress towards Hadwiger's conjecture ⋮ On the choosability of \(H\)-minor-free graphs ⋮ Extremal functions for sparse minors

This page was built for publication: The extremal function for Petersen minors