If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.

For any coloring $c:V(G) \to \chi(G)$ we define the set of fibers of $c$ by $\newcommand{\Fib}{\text{Fib}}\Fib(c) = \big\{c^{-1}(\{\alpha\}):\alpha \in \kappa\big\}$.

Note that if $V(G)$ is non-empty, then so is every member of $\Fib(c)$.

We say that a coloring $c_0:V(G) \to\chi(G)$ is optimal if $|\Fib(c_0)\setminus \Fib(c)| \leq |\Fib(c)\setminus \Fib(c_0)|$ for every coloring $c:V(G)\to \chi(G)$.

Question. Does every graph, finite or infinite, have an optimal coloring?