Induced subgraph density. II. Sparse and dense sets in cographs
A well-known theorem of Rödl says that for every graph H, and every ε > 0, there exists δ > 0 such that if G does not contain an induced copy of H, then there exists X ⊆ V (G) with |X| ≥ δ|G| such that one of G[X], G[X] has edge-density at most ε. But how does δ depend on ε? Fox and Sudakov co...
Main Authors: | Fox, J, Nguyen, T, Scott, A, Seymour, P |
---|---|
Format: | Journal article |
Language: | English |
Published: |
Elsevier
2024
|
Similar Items
-
Graphic Splitting of Cographic Matroids
by: Pirouz Naiyer
Published: (2015-02-01) -
Defining and identifying cograph communities in complex networks
by: Songwei Jia, et al.
Published: (2015-01-01) -
Graphic and Cographic Г-Extensions of Binary Matroids
by: Borse Y.M., et al.
Published: (2018-11-01) -
Dense subgraphs in random graphs
by: Balister, P, et al.
Published: (2019) -
The component structure of dense random subgraphs of the hypercube
by: McDiarmid, C, et al.
Published: (2021)