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?

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?

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.

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 maximally efficient 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 a maximally efficient coloring?

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?