Explicit 3-colorings for exponential graphs

08/27/2018
by   Adrien Argento, et al.
0

Let H=(V,E) denote a simple, undirected graph. The 3-coloring exponential graph on H is the graph whose vertex set corresponds to all (not necessarily proper) 3-colorings of H. We denote this graph by K_3^H. Two vertices of K_3^H, corresponding to colorings f and g of H, are connected by an edge in K_3^H if f(i) ≠ g(j) for all ij ∈ E. El-Zahar and Sauer showed that when H is 4-chromatic, K_3^H is 3-chromatic el1985chromatic. Based on this work, Tardif gave an algorithm to (properly) 3-color K_3^H whose complexity is polynomial in the size of K_3^H tardifAlg. Tardif then asked if there is an algorithm in which the complexity of assigning a color to a vertex of K_3^H is polynomial in the size of H. We present such an algorithm, answering Tardif's question affirmatively.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset