NUMBER OF CLIQUES IN GRAPHS WITH A FORBIDDEN SUBDIVISION

Cited 4 time in webofscience Cited 0 time in scopus
  • Hit : 323
  • Download : 0
We prove that for all positive integers t, every n-vertex graph with no K-t-subdivision has at most 2(50t)n cliques. We also prove that asymptotically, such graphs contain at most 2(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-t-minor is at most 2(ct)n for some constant c.
Publisher
SIAM PUBLICATIONS
Issue Date
2015-10
Language
English
Article Type
Article
Citation

SIAM JOURNAL ON DISCRETE MATHEMATICS, v.29, no.4, pp.1999 - 2005

ISSN
0895-4801
DOI
10.1137/140979988
URI
http://hdl.handle.net/10203/207863
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 4 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0