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$?



Coloring graph such that the coloring classes are not maximal independent sets
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.)


