Reconfiguring Graph Colorings

Graph coloring has been studied for a long time and continues to receive \ninterest within the research community \\cite{kubale2004graph}. It has applications \nin scheduling \\cite{daniel2004graph}, timetables, and compiler register \nallocation \\cite{lewis2015guide}. The most popular variant of graph coloring, \nk-coloring, can be thought of as an assignment of $k$ colors to the vertices of a \ngraph such that adjacent vertices are assigned different colors. \n \nReconfiguration problems, typically defined on the solution space of search problems, \nbroadly ask whether one solution can be transformed to another solution using \nstep-by-step transformations, when constrained to one or more specific transformation \nsteps \\cite{van2013complexity}. One well-studied reconfiguration problem is the \nproblem of deciding whether one k-coloring can be transformed to another k-coloring \nby changing the color of one vertex at a time, while always maintaining a k-coloring \nat each step. \n \nWe consider two variants of graph coloring: acyclic coloring and equitable \ncoloring, and their corresponding reconfiguration problems. A k-acylic coloring is \na k-coloring where there are more than two colors used by the vertices of each \ncycle, and a k-equitable coloring is a k-coloring such that each color class, which is \ndefined as the set of all vertices with a particular color, is nearly the same \nsize as all others. \n \nWe show that reconfiguration of acyclic colorings is PSPACE-hard, and that for \nnon-bipartite graphs with chromatic number 3 there exist two k-acylic colorings \n$f_s$ and $f_e$ such that there is no sequence of transformations that can \ntransform $f_s$ to $f_e$. We also consider the problem of whether two \nk-acylic colorings can be transformed to each other in at most $\\ell$ steps, and \nshow that it is in XP, which is the class of algorithms that run in time \n$O(n^{f(k)})$ for some computable function $f$ and parameter $k$, where in this \ncase the parameter is defined to be the length of the reconfiguration sequence \nplus the length of the longest induced cycle. \n \nWe also show that the reconfiguration of equitable colorings is PSPACE-hard \nand W[1]-hard with respect to the number of vertices with the same color. We \ngive polynomial-time algorithms for Reconfiguration of Equitable Colorings when \nthe number of colors used is two and also for paths when the number of colors \nused is three.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.