Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 1 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|improve this answer

Your Answer

 
discard

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.