Recoloring Directed Graphs

• Stefan Felsner ^[1] ; Clemens Huemer ^[2] ; Maria Saumell ^[2]
  1. [1] Technical University of Berlin

     Technical University of Berlin

     Berlin, Stadt, Alemania

     
  2. [2] Universitat Politècnica de Catalunya

     Universitat Politècnica de Catalunya

     Barcelona, España

     
• Localización: XIII Encuentros de Geometría Computacional: Zaragoza, del 29 de junio al 1 de julio de 2009 / Alfredo García Olaverri (ed. lit.) , Javier Tejel Altarriba (ed. lit.) , 2009, ISBN 978-84-92774-11-1, págs. 91-97
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

  • Let G be a directed graph and k a positive integer. We define the k-color graph of G (Dk(G) for short) as the directed graph having all k-colorings of G as node set, and where two k-colorings and ' are joined by a directed edge ! ' if ' is obtained from by choosing a vertex v and recoloring v so that its color is different from the colors of all its out-neighbors. We investigate reachability questions in Dk(G). In particular we want to know whether a fixed legal k′-coloring of G with k′ k is reachable in Dk(G) from every possible initial k-coloring . Interesting instances of this problem arise when G is planar and the orientation is an arbitrary -orientation for fixed . Our main result is that reachability can be guaranteed if the orientation has maximal out-degree k − 1 and an accessible pseudo-sink.