Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree

DOI10.1007/s00493-004-0017-8zbMath1056.05082OpenAlexW1965246637MaRDI QIDQ705743

Deryk Osthus, Daniela Kühn

Publication date: 14 February 2005

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-004-0017-8

zbMATH Keywords

average degreegraph embeddingMader theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case ⋮ Tree-width dichotomy ⋮ The chromatic number of graphs with no induced subdivision of \(K_4\) ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Clique cutsets beyond chordal graphs ⋮ Complete acyclic colorings ⋮ Induced subdivisions and bounded expansion ⋮ Triangle‐free graphs with large chromatic number and no induced wheel ⋮ The chromatic number of {ISK4, diamond, bowtie}‐free graphs ⋮ Some remarks on graphs with no induced subdivision of \(K_4\) ⋮ Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs ⋮ Amalgams and χ-Boundedness ⋮ Chromatic number of ISK4-free graphs ⋮ Hitting all maximum stable sets in \(P_5\)-free graphs ⋮ Graphs of large chromatic number ⋮ On graphs with no induced subdivision of \(K_4\) ⋮ Topological minors in bipartite graphs ⋮ On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph ⋮ Regular partitions of gentle graphs ⋮ Implicit representations and factorial properties of graphs ⋮ The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs ⋮ A Class of Three‐Colorable Triangle‐Free Graphs ⋮ A Separator Theorem for String Graphs and its Applications ⋮ A Separator Theorem for String Graphs and Its Applications ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Dense Induced Subgraphs of Dense Bipartite Graphs ⋮ In absence of long chordless cycles, large tree-width becomes a local phenomenon ⋮ From \(\chi\)- to \(\chi_p\)-bounded classes ⋮ Subdivisions of a large clique in \(C_6\)-free graphs

This page was built for publication: Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree