0
$\begingroup$

A graph with chromatic number k is definite if for each vertex $v$, $ChromaticNumber(G-v) < k$. Prove that each graph with chromatic number $k$ has a definite induced sub-graph with chromatic number $k$.

Any idea how can i start the proof?

$\endgroup$
  • $\begingroup$ As a side note, the commonly accepted terminology for "definite" is "vertex-critical", or "$k$-vertex-critical" if $k$ is known. $\endgroup$ – Misha Lavrov Nov 13 '18 at 18:38
0
$\begingroup$

Let $S$ be a maximal set of vertices such that $G \setminus S$ is $k$-colorable (but not $(k-1)$-colorable) but $G \setminus S'$ is $k'$-colorable for some $k' < k$. There clearly exists such an $S$ as removing all but $k-1$ vertices will make the graph $k'$-colorable for some $k' < k$ [make sure you see this indeed implies existence of such an $S$]

Then $G \setminus S$ is definite.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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