Antag att vi får en graf G tillsammans med två ordentliga vertex k-färger av G, α och β. Hur lätt kan vi avgöra om det är möjligt att omvandla α till β genom att omfärga hörn av G en i taget, se till att vi alltid har en korrekt k-färgning av G? Detta beslutsproblem är trivialt för k = 2, och decidable i polynom tid för k = 3. Här bevisar vi att det är PSPACE-komplett för alla k ≥ 4. I synnerhet visar vi att problemet fortfarande PSPACE-komplett för bipartit grafer, samt för: (i) planar grafer och 4 ≤ k ≤ 6, och (ii) bipartit planar grafer och k = 4. Dessutom är k-värdena i (i) och (ii) snäva, i den meningen att det alltid är möjligt att omfärga α till β för större värden av k. Vi ställer också ut, för varje k ≥ 4, en klass av grafer {G N,k : N  till N * }, tillsammans med två k-färger för varje G N,k, sådan att det minsta antalet omfärgning steg som krävs för att omvandla den första färgen till den andra är superpolynomial i storleken på grafen: det minsta antalet steg är  och (2 N ), medan storleken på G N är O(N 2 ). Detta är i skarp kontrast till k = 3 fall, där det är känt att det minsta antalet omfärgning steg är som mest kvadratisk i antalet hörn. Vi visar också att en klass av bipartit grafer kan konstrueras med denna egenskap, och att (i) för 4 ≤ k ≤ 6 planar grafer och (ii) för k = 4 bipartit planar grafer kan konstrueras med denna egenskap. Detta ger en anmärkningsvärd överensstämmelse mellan problemets användbarhet och dess underliggande struktur.
Problemet förblir PSPACE-komplett för bipartit grafer när k ≥ 4, för plana grafer när 4 ≤ k ≤ 6 och för planar bipartit grafer för k = 4 REF.
Finding Paths between Graph Colourings : PSPACE-completeness and Superpolynomial Distances
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}