Induced subgraph density. II. Sparse and dense sets in cographs

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

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron:	Fox, J, Nguyen, T, Scott, A, Seymour, P
Fformat:	Journal article
Iaith:	English
Cyhoeddwyd:	Elsevier 2024

Eitemau Tebyg

Apex Graphs and Cographs
gan: Jagdeep Singh, et al.
Cyhoeddwyd: (2024-01-01)

Sombor characteristic values of cographs
gan: Zahid Raza, et al.
Cyhoeddwyd: (2024-10-01)

Graphic Splitting of Cographic Matroids
gan: Pirouz Naiyer
Cyhoeddwyd: (2015-02-01)

Dense subgraphs in random graphs
gan: Balister, P, et al.
Cyhoeddwyd: (2019)

The component structure of dense random subgraphs of the hypercube
gan: McDiarmid, C, et al.
Cyhoeddwyd: (2021)

An efficient g-centroid location algorithm for cographs
gan: V. Prakash
Cyhoeddwyd: (2005-01-01)

Graphic and Cographic Г-Extensions of Binary Matroids
gan: Borse Y.M., et al.
Cyhoeddwyd: (2018-11-01)

Defining and identifying cograph communities in complex networks
gan: Songwei Jia, et al.
Cyhoeddwyd: (2015-01-01)

Secure total domination in chain graphs and cographs
gan: Anupriya Jha
Cyhoeddwyd: (2020-09-01)

A Diagonalization Algorithm for the Distance Matrix of Cographs
gan: Zhibin Du
Cyhoeddwyd: (2018-01-01)

Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures
gan: Chudnovsky, M, et al.
Cyhoeddwyd: (2016)

Counting subgraphs in somewhere dense graphs
gan: Bressan, M, et al.
Cyhoeddwyd: (2024)

Counting subgraphs in somewhere dense graphs
gan: Bressan, M, et al.
Cyhoeddwyd: (2023)

Largest sparse subgraphs of random graphs.
gan: Fountoulakis, N, et al.
Cyhoeddwyd: (2011)

Largest sparse subgraphs of random graphs
gan: Mcdiarmid, C, et al.
Cyhoeddwyd: (2012)

Largest sparse subgraphs of random graphs
gan: Fountoulakis, N, et al.
Cyhoeddwyd: (2014)

Induced subgraphs of induced subgraphs of large chromatic number
gan: Girao, A, et al.
Cyhoeddwyd: (2023)

Families of Integral Cographs within a Triangular Array
gan: Ching Hsin-Yun, et al.
Cyhoeddwyd: (2020-12-01)

Induced subgraphs of graphs with large chromatic number. VI. Banana trees
gan: Scott, A, et al.
Cyhoeddwyd: (2020)

Induced subgraphs of graphs with large chromatic number. XIII. New brooms
gan: Scott, A, et al.
Cyhoeddwyd: (2019)

Induced subgraphs of graphs with large chromatic number IX: rainbow paths
gan: Scott, A, et al.
Cyhoeddwyd: (2017)

Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes
gan: Scott, A, et al.
Cyhoeddwyd: (2018)

Induced subgraphs of graphs with large chromatic number. I. Odd holes
gan: Scott, A, et al.
Cyhoeddwyd: (2015)

Induced subgraphs of graphs with large chromatic number. XI. orientations
gan: Chudnovsky, M, et al.
Cyhoeddwyd: (2018)

Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture
gan: Scott, A, et al.
Cyhoeddwyd: (2020)

Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
gan: Scott, A, et al.
Cyhoeddwyd: (2019)

Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
gan: Chudnovsky, M, et al.
Cyhoeddwyd: (2021)

Induced subgraphs of graphs with large chromatic number. III. Long holes
gan: Chudnovsky, M, et al.
Cyhoeddwyd: (2016)

Induced subgraphs of graphs with large chromatic number. XII. Distant stars
gan: Chudnovsky, M, et al.
Cyhoeddwyd: (2019)

Searching social networks-dense subgraph discovery
gan: Kannan, Siddharth.
Cyhoeddwyd: (2012)

Sparse Subgraph Prediction Based on Adaptive Attention
gan: Weijun Li, et al.
Cyhoeddwyd: (2023-07-01)

A linear algorithm for obtaining the Laplacian eigenvalues of a cograph
gan: Chen Guantao, et al.
Cyhoeddwyd: (2024-09-01)

Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
gan: Chudnovsky, M, et al.
Cyhoeddwyd: (2019)

Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
gan: Chudnovsky, M, et al.
Cyhoeddwyd: (2019)

Analysis of size of the largest dense subgraph of random hypergraph
gan: N. N. Kuzyrin, et al.
Cyhoeddwyd: (2018-10-01)

Abnormal Trajectory Detection Based on a Sparse Subgraph
gan: Xujun Zhao, et al.
Cyhoeddwyd: (2020-01-01)

On Induced Subgraphs with All Degrees Odd
gan: Scott, A
Cyhoeddwyd: (2001)

Finite groups whose coprime graph is split, threshold, chordal, or a cograph
gan: Jin Chen, et al.
Cyhoeddwyd: (2024-10-01)

Large Induced Subgraphs with All Degrees Odd
gan: Scott, A
Cyhoeddwyd: (1992)

Protein complex prediction via dense subgraphs and false positive analysis.
gan: Cecilia Hernandez, et al.
Cyhoeddwyd: (2017-01-01)