Planar graphs with the maximum number of induced 6-cycles (Q6197310): Difference between revisions

Summary: For large \(n\) we determine the maximum number of induced 6-cycles which can be contained in a planar graph on \(n\) vertices, and we classify the graphs which achieve this maximum. In particular we show that the maximum is achieved by the graph obtained by blowing up three pairwise non-adjacent vertices in a 6-cycle to sets of as even size as possible, and that every extremal example closely resembles this graph. This extends previous work by the author [``Planar graphs with the maximum number of induced 4-cycles or 5-cycles'', Preprint, \url{arXiv:2108.00526}] which solves the problem for 4-cycles and 5-cycles. The 5-cycle problem was also solved independently by \textit{D. Ghosh} et al. [J. Graph Theory 99, No. 3, 378--398 (2022; Zbl 1522.05206)].