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...
| Huvudupphovsmän: | , , , |
|---|---|
| Materialtyp: | Journal article |
| Språk: | English |
| Publicerad: |
Elsevier
2023
|