Graph Theory and Combinatorics Seminar
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- Gregory Hall 327
- Date
- Oct 22, 2024 1:00 pm
- Speaker
- Michael Wigal (UIUC)
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Views
- 10
- Originating Calendar
- Combinatorics Research Area Calendar
Speaker: Michael C. Wigal (UIUC)
Title: Long cycles in essentially 4-connected graphs
Abstract: Tutte proved that every 4-connected planar graph is Hamiltonian, but there are 3-connected planar graphs whose longest cycles have length which are sublinear in the number of vertices. We show that every essentially 4-connected planar $n$-vertex graph with $n \ge 6$ vertices has a cycle of length at least $(2n + 6)/3$. This bound is best possible. Our techniques involve proving a quantitative version of a result of Thomassen regarding Tutte paths.Joint work with Xingxing Yu.