Leírás
In this talk, we concentrate on determining the maximum number of edges in hexagon-free planar graphs and we would like to show the nature of these problems (difficulties, necessary results, and conjectures). Let \({\rm ex}_{\mathcal{P}}(n,H)\) denote the maximum number of edges in an \(n\)-vertex planar graph which does not contain \(H\) as a subgraph. Dowden obtained exact results for \({\rm ex}_{\mathcal{P}}(n,C_4)\) and \({\rm ex}_{\mathcal{P}}(n,C_5)\), but the case of longer cycles remained open. Later on, Y. Lan, et al. proved that \({\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}\). In this talk, I plan to sketch the proof of the tight result \({\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7\), for all \(n\geq 18\) and show infinitely many examples when it is tight. Based on them, we raise a conjecture on \({\rm ex}_{\mathcal{P}}(n,C_k)\), for \(k \geq 7\)
Joint work with Debarun Ghosh (CEU), Ryan R. Martin (Iowa State Univ.), AddisuPaulos (CEU), Chuanqi Xiao(CEU)
Recording available at:
https://old.renyi.hu/seminars/ErvinGyori_2020_04_30_%20Hexagon-free_planar_graphs.mp4