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 |
| _version_ | 1826191024417931264 |
|---|---|
| author | Lee, Choongbum Oum, Sang-il |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Lee, Choongbum Oum, Sang-il |
| author_sort | Lee, Choongbum |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:49:15Z |
| format | Article |
| id | mit-1721.1/101894 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:49:15Z |
| publishDate | 2016 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/1018942022-09-23T14:46:53Z Number of Cliques in Graphs with a Forbidden Subdivision Lee, Choongbum Oum, Sang-il Massachusetts Institute of Technology. Department of Mathematics Lee, Choongbum 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. National Science Foundation (U.S.) (Grant DMS-1362326) 2016-03-28T18:32:08Z 2016-03-28T18:32:08Z 2015-10 2015-08 Article http://purl.org/eprint/type/JournalArticle 0895-4801 1095-7146 http://hdl.handle.net/1721.1/101894 Lee, Choongbum, and Sang-il Oum. “Number of Cliques in Graphs with a Forbidden Subdivision.” SIAM Journal on Discrete Mathematics 29, no. 4 (January 2015): 1999–2005. © 2015 Society for Industrial and Applied Mathematics https://orcid.org/0000-0002-5798-3509 en_US http://dx.doi.org/10.1137/140979988 SIAM Journal on Discrete Mathematics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics Society for Industrial and Applied Mathematics |
| spellingShingle | Lee, Choongbum Oum, Sang-il Number of Cliques in Graphs with a Forbidden Subdivision |
| title | Number of Cliques in Graphs with a Forbidden Subdivision |
| title_full | Number of Cliques in Graphs with a Forbidden Subdivision |
| title_fullStr | Number of Cliques in Graphs with a Forbidden Subdivision |
| title_full_unstemmed | Number of Cliques in Graphs with a Forbidden Subdivision |
| title_short | Number of Cliques in Graphs with a Forbidden Subdivision |
| title_sort | number of cliques in graphs with a forbidden subdivision |
| url | http://hdl.handle.net/1721.1/101894 https://orcid.org/0000-0002-5798-3509 |
| work_keys_str_mv | AT leechoongbum numberofcliquesingraphswithaforbiddensubdivision AT oumsangil numberofcliquesingraphswithaforbiddensubdivision |