Seminár z teórie grafov - František Kardoš (5.5.2022)
vo štvrtok 5.5.2022 o 9:50 hod. v miestnosti M/213
Od: Martin Škoviera
Prednášajúci: František Kardoš
Názov: Strengthening a theorem of Meyniel
Termín: 5.5.2022, 9:50 hod., M 213
For an integer k>=1 and a graph G, let K_k(G) be the graph that has vertex set all proper k-colorings of G, and an edge between two vertices x and y whenever the coloring y can be obtained from x by a single Kempe change. A theorem of Meyniel from 1978 states that K_5(G) is connected, with diameter O(5^|V(G)|), for every planar graph G. We significantly strengthen this result, by showing that there is a positive constant c such that K_5(G) has diameter O(|V(G)|^c) for every planar graph G.
This is a joint work with Quentin Deschamps, Carl Feghali, Clément Legrand-Duchesne, and Théo Pierron.