2 problems

Let $G$ be a graph. A $4$-To-$3$ instance asks whether a proper $4$-coloring of $G$ can be transformed into a proper $3$-coloring by repeatedly recoloring one vertex while maintain…

Let $G$ be a graph and let $k$ be an integer with $k\geq 4$. A $k$-coloring of $G$ is a proper vertex coloring using colors from a set of $k$ colors, and $k$-Mixing asks whether an…