Skip to main content
1 of 2
bof
  • 13.4k
  • 2
  • 43
  • 66

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 infinite, this argument requires 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.

bof
  • 13.4k
  • 2
  • 43
  • 66