Graph Theory and Combinatorics Seminar
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- Gregory Hall 319
- Date
- Apr 27, 2023 10:30 am
- Speaker
- Bernard Lidický
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Phone
- 217-898-4426
- Views
- 40
- Originating Calendar
- General Events - Department of Mathematics
Speaker: Bernard Lidický
Title: Embedded graph 3-coloring and flows
Abstract: A graph drawn in a surface is a near-quadrangulation if the sum of the lengths of the faces different from 4-faces is bounded by a fixed constant. We leverage duality between colorings and flows to design an efficient algorithm for 3-precoloring-extension in near-quadrangulations of orientable surfaces. Furthermore, we use this duality to strengthen previously known sufficient conditions for 3-colorability of triangle-free graphs drawn in orientable surfaces. This is joint work with Caroline Bang, Zdeněk Dvořák and Emily Heath.