Topological Cliques in Graphs

DOI10.1017/S0963548300001140MaRDI QIDQ4305319zbMATH OpenOpenAlexFDO

Authors János Komlós, Endre Szemerédi

Publication date 20 March 1995

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548300001140

zbMATH Keywords

expanderrandom graphsubdivisiontopological clique

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Recommendations

• Large Topological Cliques in Graphs Without a 4-Cycle
• A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
• Improved Bounds for Topological Cliques in Graphs of Large Girth
• Balanced Subdivisions of a Large Clique in Graphs with High Average Degree
• Logarithmically small minors and topological minors

Cites work

• Hinreichende Bedingungen für die Existenz von Teilgraphen, die zu einem vollständigen Graphen homöomorph sind
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• On the conjecture of Hajos
• Topological cliques of random graphs

Cited in

(35)

• Subdivisions of a large clique in \(C_6\)-free graphs
• On nowhere dense graphs
• Highly linked graphs
• Extremal connectivity for topological cliques in bipartite graphs
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• scientific article; zbMATH DE number 1047738 (Why is no real title available?)
• Finding and using expanders in locally sparse graphs
• Large Topological Cliques in Graphs Without a 4-Cycle
• Topological cliques in graphs II
• Well-mixing vertices and almost expanders
• Topology of clique complexes of line graphs
• Crux and Long Cycles in Graphs
• Logarithmically small minors and topological minors
• Improved Bounds for Topological Cliques in Graphs of Large Girth
• Disjoint isomorphic balanced clique subdivisions
• Rainbow clique subdivisions
• Balanced Subdivisions of a Large Clique in Graphs with High Average Degree
• A solution to Erdős and Hajnal’s odd cycle problem
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Towards the Erdős-Gallai cycle decomposition conjecture
• Rainbow subdivisions of cliques
• Towards the Erdős-Gallai cycle decomposition conjecture
• Immersion of complete digraphs in Eulerian digraphs
• Separating path systems of almost linear size
• Extremal density for sparse minors and subdivisions
• Many Hamiltonian subsets in large graphs with given density
• Crux, space constraints and subdivisions
• Boxicity, poset dimension, and excluded minors
• Nearly Hamilton cycles in sublinear expanders and applications
• Extremal density for subdivisions with length or sparsity constraints
• Crux, space constraints and subdivisions (extended abstract)
• Edge-disjoint cycles with the same vertex set
• Embedding clique subdivisions via crux
• Packing subdivisions into regular graphs
• New exact values of the maximum size of graphs free of topological complete subgraphs

This page was built for publication: Topological Cliques in Graphs

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