Győri Ervin: Hexagon-free planar graphs

Description of video

Date: 4/30/20
Speaker :Győri Ervin

Keywords

    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 exP(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 exP(n,C4) and exP(n,C5), but the case of longer cycles remained open. Later on, Y. Lan, et al. proved that  exP(n,C6)18(n2)7. In this talk, I plan to sketch the proof of the tight result exP(n,C6)52n7, for all n18 and show infinitely many examples when it is tight. Based on them, we raise a conjecture on exP(n,Ck), for 

    Downloads