3n-5 edges do force a subdivision of K₅

DOI10.1007/S004930050041MaRDI QIDQ1307446zbMATH OpenOpenAlexWikidataFDO

Authors W. Mader

Publication date 31 October 1999

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930050041

zbMATH Keywords

extremal graph theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35)

Review text

It is shown that a graph on at least 3 vertices and with \(3n-5\) edges contains a subdivision of \(K_5\). This was conjectured by Dirac in 1964. The proof is fairly involved.

Recommendations

• Do 3n − 5 edges force a subdivision ofK5?
• K₅-Subdivisions in Graphs
• Graphs with \(3n-6\) edges not containing a subdivision of \(K_5\)
• An extremal problem for subdivisions ofK?5

Cited in

(34)

• Removable edges in a \(k\)-connected graph and a construction method for \(k\)-connected graphs
• Six variations on a theme: almost planar graphs
• The edge colorings of \(K_5\)-minor free graphs
• Locally Hamiltonian graphs and minimal size of maximal graphs on a surface
• Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\)
• Tuza's conjecture for graphs with maximum average degree less than 7
• Subdivisions in apex graphs
• Reducing Hajós' 4-coloring conjecture to 4-connected graphs
• Counting \(K_4\)-subdivisions
• Graphs with \(3n-6\) edges not containing a subdivision of \(K_5\)
• Graphs containing topological H
• Subdivisions of \(K_{5}\) in graphs embedded on surfaces with face-width at least 5
• STRUCTURE OF THE EXTREMAL FAMILY EX(n;TKp)
• K₆-minors in triangulations and complete quadrangulations
• Do 3n − 5 edges force a subdivision ofK5?
• Remarks on a conjecture of Barát and Tóth
• An extremal problem for subdivisions ofK?5
• K₅^--subdivision in 4-connected graphs
• Saturation numbers for families of graph subdivisions
• Topological minors in line graphs -- a proof of Zha's conjecture
• An advance in infinite graph models for the analysis of transportation networks
• Unique Colorability and Clique Minors
• Connectivity for kite-linked graphs
• On a coloring conjecture of Hajós
• Independent paths and \(K_{5}\)-subdivisions
• Wheels in planar graphs and Hajós graphs
• 4‐Separations in Hajós graphs
• A decomposition method on solving the linear arboricity conjecture
• Topological minors in bipartite graphs
• Some remarks on Hajós' conjecture
• What is on his mind?
• The Kelmans-Seymour conjecture. IV: A proof
• New exact values of the maximum size of graphs free of topological complete subgraphs
• On embeddability and stresses of graphs

This page was built for publication: \(3n-5\) edges do force a subdivision of \(K_5\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1307446)