Research Projects

The topic of graph coloring plays a prominent role in the field of graph theory and algorithms. Recent research shows that coloring problems continue to attract significant attention. A k-coloring of a graph G is a mapping of its vertex set V(G) to a set of k colors such that adjacent vertices receive different colors. The chromatic number χ(G) is the smallest k for which such a coloring exists. Garey et al. (1974) showed that determining whether G admits a k-coloring is NP-complete for all k greater than 2. Due to this hardness, researchers have focused on restricted graph classes to design efficient coloring algorithms. Reconfiguration problems are defined on the solution space of a problem where each configuration is a feasible solution. These problems have real-world applications such as maintaining firewalls in dynamic networks, frequency assignment in mobile networks, modeling Glauber dynamics and Markov chains in statistical physics, and motion planning in robotics and 3D printing. Given a graph G, the reconfiguration graph of k-colorings, denoted R{k}(G), has as vertices the k-colorings of G. Two colorings are adjacent in R{k}(G) if they differ on exactly one vertex. A graph G is said to be k-mixing if R{k}(G) is connected. If G is c-mixing for all c strictly greater than χ(G), then G is said to be recolorable. For a graph G and a k-coloring f of V (G), a Kempe chain is a component in G induced by those vertices which are colored i or j, for some fixed choice of i and j. Consider the reconfiguration graph Kempe{k}(G) with vertices all k-colorings of graph G where two k-colorings f and g are adjacent if g can be obtained from f by a single Kempe swap (switching of colors on the vertices of a Kempe chain). Kempe reconfiguration graphs have received considerable attention [survey by van den Heuvel (2013)]. This proposal focuses on reconfiguration problems in graphs motivated by such applications, particularly the connectivity and the structural properties of the reconfiguration graph in certain hereditary graph classes. Hereditary graph classes (those closed under taking induced subgraphs) include perfect graphs and graphs defined by forbidden induced subgraphs. A graph is perfect if every induced subgraph H satisfies χ(H) = ω(H) (the clique number of H). The celebrated Strong Perfect Graph Theorem (Chudnovsky et al.) characterizes perfect graphs via forbidden subgraphs. Recent work, including the PI’s doctoral thesis (2024), has studied the structure of reconfiguration graphs for several perfect graph subclasses, including bipartite, split, chordal, and P₃-free graphs. We have identified new classes of graphs (defined by forbidden induced subgraphs) that are recolorable. Our main research objectives are: • Develop algorithms for hereditary graph classes, to determine whether a graph in it is c-mixing. • Explore key open problems and conjectures about reconfiguration graphs of k-colorings.