Spanning 3-colourable subgraphs of small bandwidth in dense graphs

DOI10.1016/j.jctb.2007.11.005zbMath1149.05021OpenAlexW2083035128MaRDI QIDQ933679

Julia Böttcher, Mathias Schacht, Anusch Taraz

Publication date: 24 July 2008

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.2007.11.005

zbMATH Keywords

bandwidthregularity lemmaspanning subgraphsextremal graph theory

Mathematics Subject Classification ID

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

Related Items (10)

Stability for the Erdős-Rothschild problem ⋮ On a degree sequence analogue of Pósa's conjecture ⋮ On sufficient conditions for spanning structures in dense graphs ⋮ Embedding spanning subgraphs of small bandwidth ⋮ Bounded-Degree Spanning Trees in Randomly Perturbed Graphs ⋮ On Degree Sequences Forcing The Square of a Hamilton Cycle ⋮ The bandwidth theorem for locally dense graphs ⋮ Proof of the bandwidth conjecture of Bollobás and Komlós ⋮ Bandwidth theorem for random graphs ⋮ Forcing spanning subgraphs via Ore type conditions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Ramsey number of a graph with bounded maximum degree
• Almost \(H\)-factors in dense graphs
• Proof of the Seymour conjecture for large graphs
• Blow-up lemma
• How tight is the Bollobás-Komlós conjecture?
• Tiling Turán theorems
• 2-factors in dense bipartite graphs
• Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three
• The square of paths and cycles
• 2-factors in dense graphs
• \(H\)-factors in dense graphs
• Hamiltonian square-paths
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Large planar subgraphs in dense graphs
• Spanning Trees in Dense Graphs
• Matchings Meeting Quotas and Their Impact on the Blow-Up Lemma
• Critical chromatic number and the complexity of perfect packings in graphs
• An algorithmic version of the blow-up lemma
• The Blow-up Lemma
• Embedding Arbitrary Graphs of Maximum Degree Two
• The Algorithmic Aspects of the Regularity Lemma
• Proof of a tiling conjecture of Komlós
• On the square of a Hamiltonian cycle in dense graphs
• Spanning triangulations in graphs
• On the maximal number of independent circuits in a graph
• Some Theorems on Abstract Graphs
• On the structure of linear graphs
• Proof of the Alon-Yuster conjecture

This page was built for publication: Spanning 3-colourable subgraphs of small bandwidth in dense graphs