# Coloring graph such that the coloring classes are not maximal independent sets

Let $G$ be a (finite or infinite) simple graph. We let $\mathrm{Ind}(G)$ be the collection of independent sets. For any cardinal $\kappa$ and coloring map $\chi: G\to \kappa$ we have $\chi^{-1}(\{\beta\}) \in \mathrm{Ind}(G)$ for all $\beta \in \kappa$.

Let $\mathrm{Max}(\mathrm{Ind}(G))$ be the set of maximal independent sets of $G$ and suppose $\kappa_0$ is the smallest cardinal such that there is a coloring map $\chi: G\to \kappa_0$.

Question: Is it possible that for all coloring maps $\chi: G\to \kappa_0$ we have $\{\chi^{-1}(\{\beta\}) : \beta\in\kappa_0\} \cap \mathrm{Max}(\mathrm{Ind}(G)) = \emptyset$?

-

Of course not. Consider any graph $G$ and any coloring map $\chi:G\to\kappa_0$. Choose $\beta\in\kappa_0$, extend the independent set $\chi^{-1}(\beta)$ to a maximal independent set $S$, and define a new coloring map $\chi':G\to\kappa_0$ by setting $\chi'(v)=\beta$ if $v\in S$ and $\chi'(v)=\chi(v)$ otherwise.
If $G$ is uncountable, this argument may require the axiom of choice. Without choice, the graph may have no maximal independent sets; for that matter, the chromatic number $\kappa_0$ may fail to exist. (There is no problem if the vertices of $G$ can be well-ordered, e.g., if $G$ is countable.)