0
$\begingroup$

Let $G$ be a graph and $M\subseteq V(G)$ be a maximal independent set. Is there a coloring $c:V(G)\to\chi(G)$ such that $c$ is constant on $M$?

(The answer is positive for graphs with infinite chromatic number: Given any coloring $c:V(G)\to\chi(G)$ define a new coloring $c'$ by $c(m) = 0$ for $m\in M$ and $c'(x) = c(x)+1$ for $x\in $V(G)\setminus M$.)

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
1
$\begingroup$

Pick some bipartite graph A,B and add a huge new independent set of vertices connecting half of them with all of A and half of them with all of B. The resulting graph is bipartite, but there is no 2-coloring of it which is constant on the new set.

Improve this answer
$\endgroup$
3
$\begingroup$

No. Take $V=\{1,2,3,4\}$, $E=\{\{1,2\},\{2,3\},\{3,4\}\}$. Then $G$ is bipartite, and $M=\{1,4\}$ is a maximal independent set.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .