On 4-colorable robust critical graphs
Mark Anderson, Robert C. Brigham, Ronald D. Dutton, Richard P. Vitray, Jay Yellen · Discrete Mathematics Letters · 2021
Given a proper k-coloring of a graph G, a vertex v is locally recolorable if there is a proper k-coloring of the graph that changes the color of v and limits any other color changes to the neighbors of v.The coloring is robust if every vertex is locally recolorable.The robust chromatic number of G, χR(G), is the smallest number k for which G has a robust k-coloring.If χR(G) = χ(G), the graph is χ-robust and if deleting any vertex of a χ-robust graph decreases χR(G), the graph is χ-robustcritical.We conjecture that only complete graphs are χ-robust-critical.This paper investigates this conjecture for χ = 4 and supports the conjecture for a large class of such graphs.Furthermore, conditions that must be satisfied for such graphs are determined.