Sparse partition universal graphs for graphs of bounded degree

DOI10.1016/J.AIM.2011.01.004MaRDI QIDQ633606zbMATH OpenOpenAlexWikidataFDO

Authors Yoshiharu Kohayakawa, Vojtěch Rödl, M. Schacht, Endre Szemerédi

Publication date 29 March 2011

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aim.2011.01.004

zbMATH Keywords

random graphsregularity Lemmainheritance of regularitysize-Ramsey numbersuniversal graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55)

Recommendations

• Sparse multipartite graphs as partition universal for graphs with bounded degree
• Sparse universal graphs for bounded‐degree graphs
• Partitioning sparse graphs into an independent set and a forest of bounded degree
• Explicit sparse almost-universal graphs for \(\mathcal G (n, \frac kn)\)
• Partitioning sparse graphs into an independent set and a graph with bounded size components
• Sparse universal graphs
• scientific article; zbMATH DE number 1833411
• Sparse universal graphs for planarity
• Judicious partitions of bounded‐degree graphs
• On partitions of graphs under degree constraints

Cites work

• scientific article; zbMATH DE number 5764887 (Why is no real title available?)
• scientific article; zbMATH DE number 4029619 (Why is no real title available?)
• scientific article; zbMATH DE number 3724483 (Why is no real title available?)
• scientific article; zbMATH DE number 16104 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1944144 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2086426 (Why is no real title available?)
• scientific article; zbMATH DE number 1833411 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• An algorithmic version of the blow-up lemma
• An ergodic Szemerédi theorem for commuting transformations
• Blow-up lemma
• Expanding graphs contain all small trees
• Hypergraph regularity and the multidimensional Szemerédi theorem
• On graphs with small subgraphs of large chromatic number
• On sets of integers containing k elements in arithmetic progression
• On size Ramsey number of paths, trees, and circuits. I
• On size Ramsey numbers of graphs with bounded degree
• Paths in graphs
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Regular pairs in sparse random graphs I
• Regularity Lemma for k-uniform hypergraphs
• Small subsets inherit sparse \(\varepsilon\)-regularity
• Spanning subgraphs of random graphs
• Sparse universal graphs for bounded‐degree graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• The Induced Size-Ramsey Number of Cycles
• The Ramsey number of a graph with bounded maximum degree
• The asymptotic number of labeled graphs with given degree sequences
• The counting lemma for regular k‐uniform hypergraphs
• The hypergraph regularity method and its applications
• The size Ramsey number
• The size-Ramsey number of trees
• The sparse regularity lemma and its applications

Cited in

(23)

• The size‐Ramsey number of cubic graphs
• The vertex size-Ramsey number
• Constructive lower bounds for off-diagonal Ramsey numbers
• Lower bounds of size Ramsey number for graphs with small independence number
• The size-Ramsey number of powers of bounded degree trees
• Rolling backwards can move you forward: on embedding problems in sparse expanders
• The size Ramsey number of short subdivisions of bounded degree graphs
• Multicolor list Ramsey numbers grow exponentially
• The size-Ramsey number of powers of bounded degree trees
• On the size-Ramsey number of grids
• Bipartite Ramsey numbers of cycles for random graphs
• Extremal results in sparse pseudorandom graphs
• Random bipartite Ramsey numbers of long cycles
• Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
• On the size-Ramsey number of grid graphs
• Size Ramsey number of bounded degree graphs for games
• The multicolour size-Ramsey number of powers of paths
• Sparse universal graphs
• Interview with David Conlon
• Almost-spanning universality in random graphs
• Triangle-free subgraphs of random graphs
• Sparse multipartite graphs as partition universal for graphs with bounded degree
• Bipartite Ramsey numbers of paths for random graphs

This page was built for publication: Sparse partition universal graphs for graphs of bounded degree

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