Large planar subgraphs in dense graphs

DOI10.1016/j.jctb.2005.04.004zbMath1075.05045OpenAlexW2073812123MaRDI QIDQ2573646

Deryk Osthus, Anusch Taraz, Daniela Kühn

Publication date: 22 November 2005

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

Full work available at URL: https://doi.org/10.1016/j.jctb.2005.04.004

zbMATH Keywords

Regularity lemmaExtermal graph theory

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items (max. 100)

Spanning surfaces in \(3\)-graphs ⋮ Minimum Degrees for Powers of Paths and Cycles ⋮ Bandwidth, treewidth, separators, expansion, and universality ⋮ The minimum degree threshold for perfect graph packings ⋮ Maximum planar subgraphs in dense graphs ⋮ On sufficient conditions for spanning structures in dense graphs ⋮ Bounded-Degree Spanning Trees in Randomly Perturbed Graphs ⋮ A degree sequence version of the Kühn-Osthus tiling theorem ⋮ On Degree Sequences Forcing The Square of a Hamilton Cycle ⋮ Finding Triangles for Maximum Planar Subgraphs ⋮ Spanning 3-colourable subgraphs of small bandwidth in dense graphs ⋮ Proof of the bandwidth conjecture of Bollobás and Komlós ⋮ Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs ⋮ Properties of \(\pi\)-skew graphs with applications ⋮ Spanning embeddings of arrangeable graphs with sublinear bandwidth ⋮ Spanning triangulations in graphs ⋮ An Extension of the Blow-up Lemma to Arrangeable Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proof of the Seymour conjecture for large graphs
• Blow-up lemma
• Tiling Turán theorems
• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• Hamiltonian square-paths
• Spanning maximal planar subgraphs of random graphs
• A Better Approximation Algorithm for Finding Planar Subgraphs
• An algorithmic version of the blow-up lemma
• The Blow-up Lemma
• The Algorithmic Aspects of the Regularity Lemma
• Spanning triangulations in graphs
• Minimal Regular Graphs of Girths Eight and Twelve
• On Hamiltonian Regular Graphs of Girth Six
• On the maximal number of independent circuits in a graph

This page was built for publication: Large planar subgraphs in dense graphs