Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10118817 | Journal of Combinatorial Theory, Series A | 2019 | 5 Pages |
Abstract
In 1975, Pippenger and Golumbic conjectured that every n-vertex graph has at most nk/(kkâk) induced cycles of length kâ¥5. We prove that every n-vertex graph has at most 2nk/kk induced cycles of length k.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daniel Král', Sergey Norin, Jan Volec,