Seminár z teórie grafov - František Kardoš (15.10.2020)

vo štvrtok 15.10.2020 o 9:50 hod.

13. 10. 2020 13.16 hod.
Od: Martin Škoviera

Účasť na seminári je možná dištančne cez MS TEAMS. Prezenčne sa seminára môže zúčastniť najviac 5 záujemcov.

Prednášajúci: František Kardoš (FMFI UK, LABRI University of Bordeaux)

Názov: Islands in planar graphs

Termín: 15.10.2020, 9:50 hod.

Prístupový kód do MS TEAMS (pre používateľov z UK): gglxxc7
Pripojenie (pre hostí mimo UK)

Abstrakt:
Thomassen (1995) showed that every planar graph of girth at least 5 is 3-choosable (i.e., can be properly colored from any assignment of lists of at least 3 allowed colors at each vertex). However, it has been open whether this statement can be proven via reducible configurations and discharging (such an argument would be easier to generalize to coloring graphs embedded on other surfaces). We find such a proof: we show that each planar graph of girth at least 5 and minimum degree at least 3 contains a small subgraph H such that each vertex of H has at most one neighbor outside of H (an island), and we find an unavoidable set of islands which are reducible using the polynomial method of Alon and Tarsi. We also consider analogous questions for planar graphs in general, without the girth condition.

This is a joint work with Marthe Bonamy, Michelle Delcourt, Zdeněk Dvořák, and Luke Postle.