Strengthening a theorem of Meyniel
Résumé
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 α and β whenever the coloring β can be obtained from α 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.
Domaines
Informatique [cs]
Origine : Fichiers produits par l'(les) auteur(s)
licence : CC BY - Paternité
licence : CC BY - Paternité