2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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