2022/11/30 by Dibyayan Chakraborty, Chakraborty, Dibyayan, Carl Feghali +2
Computer Science · Materials Science · Chemistry · #Computational Drug Discovery Methods #Photochromic and Fluorescence Chemistry #Click Chemistry and Applications
paper · pdf · doi:10.48550/arxiv.2211.16728
A Kempe chain on colors a and b is a component of the subgraph induced by colors a and b. A Kempe change is the operation of interchanging the colors of some Kempe chain. For a list-assignment L and an L-coloring φ, a Kempe change is L-valid for φ if performing the Kempe change yields another L-coloring. Two L-colorings are L-equivalent if we can form one from the other by a sequence of L-valid Kempe changes. A degree-assignment is a list-assignment L such that L(v)≥ d(v) for every v∈ V(G). Cranston and Mahmoud (Combinatorica, 2023) asked: For which graphs G and degree-assignment L of G is it true that all the L-colorings of G are L-equivalent? We prove that for every 4-connected graph G which is not complete and every degree-assignment L of G, all L-colorings of G are L-equivalent.