Dear all,
This week's speaker is Jakub Pekárek (Charles University), winner of Jirka Matousek prize 2021. Please find the talk details below.
Best regards, Misha Tyomkyn.
-----------------------------------------------------------------------------------------------
Coloring near-quadrangulations of the torus Jakub Pekárek Charles University April 14, 2022, 12:20 in S6
Abstract The 3-colorability of triangle-free graphs is always guaranteed for graphs embedded in the plane, while NP-complete when triangles are allowed. It is known that in general for any surface, deciding 3-colorability of triangle-free graphs cannot be algorithmically hard and can be reduced to 3-coloring of near-quadrangulations of the given surface. However only for the plane and the projective plane a nice characterization of 3-colorability was known. Our focus is on the graphs embedded in the torus. We design an algorithm capable of deciding 3-colorability of near-quadrangulations in a reasonable time. Based on this result, we derive further characteristics necessary for a triangle-free graph embedded in the torus to not have a 3-coloring and design a practical algorithm for 3-coloring triangle-free graphs embedded in the torus. Based on our ideas, an algorithm for general surfaces was later derived.
Joint work with Zdeněk Dvořák
------------------------------------------------------------------------------------------------