Skip to main content
added 95 characters in body
Source Link
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 infiniteuncountable, this argument requiresmay 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.)

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.

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.)

Source Link
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.