On the Computational Complexity of the Forcing Chromatic Number

Frank Harary, Wolfgang Slany, Oleg Verbitsky

We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is $s$-chromatic if it is colorable in $s$ colors and any coloring of it uses at lea…