A bound on the inducibility of cycles

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:161

Article

Kral, Daniel^1,2  Norin, Sergey³  Volec, Jan³ 

[1] Univ Warwick, Math Inst, DIMAP, Coventry CV4 7AL, W Midlands, England

[2] Univ Warwick, Dept Comp Sci, Coventry CV4 7AL, W Midlands, England

[3] McGill Univ, Dept Math & Stat, Montreal, PQ, Canada

关键词: Extremal graph theory;    Inducibility;    Cycles;   

DOI  :  10.1016/j.jcta.2018.08.003

来源: Elsevier

【 摘 要 】

In 1975, Pippenger and Golumbic conjectured that every n-vertex graph has at most n(k)/(k(k) - k) induced cycles of length k >= 5. We prove that every n-vertex graph has at most 2n(k)/k(k) induced cycles of length k. (C) 2018 Elsevier Inc. All rights reserved.

【 授权许可】

Free