MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.