Number of Cliques in Graphs with a Forbidden Subdivision
We prove that for all positive integers t, every n-vertex graph with no K[subscript t]-subdivision has at most 2[superscript 50t]n cliques. We also prove that asymptotically, such graphs contain at most 2[superscript (5+o(1))t]n cliques, where o(1) tends to zero as t tends to infinity. This strongly...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2016
|
| Online Access: | http://hdl.handle.net/1721.1/101894 https://orcid.org/0000-0002-5798-3509 |
| Summary: | We prove that for all positive integers t, every n-vertex graph with no K[subscript t]-subdivision has at most 2[superscript 50t]n cliques. We also prove that asymptotically, such graphs contain at most 2[superscript (5+o(1))t]n cliques, where o(1) tends to zero as t tends to infinity. This strongly answers a question of Wood that asks whether the number of cliques in n-vertex graphs with no K[subscript t]-minor is at most 2[superscript ct]n for some constant c. |
|---|