If $G=(V,E)$ is a graph, we call the smallest [cardinal](https://en.wikipedia.org/wiki/Cardinal_number) $\kappa$ such that there is a [coloring map](https://en.wikipedia.org/wiki/Graph_coloring) $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? 

---------------

**Background / Motivation.** Every coloring partitions the vertex set of a graph into (independent) sets. Generally, when we deal with partitions of a given set, some partitions can be "more efficient" than others in the following sense: Consider $\omega$ along with the partitions  $P = \big\{ \{n\}  : n \in \omega  \big\}$ and
$Q = \big\{ \{0,1\} \big\}   \cup  \big\{ \{n\} : n \in \omega \setminus \{0,1\}\big\}$. Even if $|P| = |Q| = \aleph_0$, partition $Q$ is "more efficient" than $P$ because $$|Q \setminus P| = 1 < 2 = |P \setminus Q|.$$ My question is whether amongst the partitions we get from proper colorings $c:V(G) \to \chi(G)$, there is a "most efficient" one.