Strengthening Rödl's theorem
What can be said about the structure of graphs that do not contain an induced copy of some graph H? Rödl showed in the 1980s that every H-free graph has large parts that are very sparse or very dense. More precisely, let us say that a graph F on n vertices is ε-restricted if either F or its compleme...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2023
|
| _version_ | 1797110825925738496 |
|---|---|
| author | Chudnovsky, M Scott, A Seymour, P Spirkl, S |
| author_facet | Chudnovsky, M Scott, A Seymour, P Spirkl, S |
| author_sort | Chudnovsky, M |
| collection | OXFORD |
| description | What can be said about the structure of graphs that do not
contain an induced copy of some graph H? Rödl showed in the
1980s that every H-free graph has large parts that are very
sparse or very dense. More precisely, let us say that a graph F
on n vertices is ε-restricted if either F or its complement has
maximum degree at most εn. Rödl proved that for every graph
H, and every ε > 0, every H-free graph G has a linear-sized
set of vertices inducing an ε-restricted graph. We strengthen
Rödl’s result as follows: for every graph H, and all ε > 0,
every H-free graph can be partitioned into a bounded number
of subsets inducing ε-restricted graphs. |
| first_indexed | 2024-03-07T08:00:10Z |
| format | Journal article |
| id | oxford-uuid:37a0336a-57d8-42ab-94de-57fa114a2c1f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:00:10Z |
| publishDate | 2023 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:37a0336a-57d8-42ab-94de-57fa114a2c1f2023-09-26T08:45:28ZStrengthening Rödl's theoremJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:37a0336a-57d8-42ab-94de-57fa114a2c1fEnglishSymplectic ElementsElsevier2023Chudnovsky, MScott, ASeymour, PSpirkl, SWhat can be said about the structure of graphs that do not contain an induced copy of some graph H? Rödl showed in the 1980s that every H-free graph has large parts that are very sparse or very dense. More precisely, let us say that a graph F on n vertices is ε-restricted if either F or its complement has maximum degree at most εn. Rödl proved that for every graph H, and every ε > 0, every H-free graph G has a linear-sized set of vertices inducing an ε-restricted graph. We strengthen Rödl’s result as follows: for every graph H, and all ε > 0, every H-free graph can be partitioned into a bounded number of subsets inducing ε-restricted graphs. |
| spellingShingle | Chudnovsky, M Scott, A Seymour, P Spirkl, S Strengthening Rödl's theorem |
| title | Strengthening Rödl's theorem |
| title_full | Strengthening Rödl's theorem |
| title_fullStr | Strengthening Rödl's theorem |
| title_full_unstemmed | Strengthening Rödl's theorem |
| title_short | Strengthening Rödl's theorem |
| title_sort | strengthening rodl s theorem |
| work_keys_str_mv | AT chudnovskym strengtheningrodlstheorem AT scotta strengtheningrodlstheorem AT seymourp strengtheningrodlstheorem AT spirkls strengtheningrodlstheorem |