Description
Given two colorings of a graph, we consider the following question: can we re-color the graph from one coloring to the other through a series of elementary changes? Here, an elementary change, or step, consists in selecting an independent set and changing the color of each vertex to another also compatible with the colors of its neighbors. The answer is not always positive, and it is in fact a PSPACE-complete decision problem. In this talk, we try to quantify how considering a stable set at each step instead of a single vertex impacts the number of steps necessary for a re-coloring, and how much communication is needed in the LOCAL model (at each round, a vertex can only communicate with its neighbors, with no limitation as to the size of the messages nor the computation power of the vertex) to compute the re-coloring or decide there is none. We also consider the question of how many extra colors are needed to make the problem always feasible, and beyond that, how the number of necessary steps decreases with the addition of colors. The case of trees is of special interest. I will provide a collection of both positive and negative results around those questions. This a joint work with Marthe Bonamy, Paul Ouvrard, Jukka Suomela and Jara Uitto.| Aikajakso | 15 helmik. 2018 |
|---|---|
| Pidetty | ENS-Lyon, Ranska |
| Tunnustuksen arvo | Local |