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

03. 05. 2022 15.00 hod.
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.

Stránka seminára