0
$\begingroup$

How to show that if G has an induced subgraph which is a complete graph on n vertices, then the chromatic number is at least $\chi(G)\ge n$.

$\endgroup$
  • 1
    $\begingroup$ More generally, if $H$ is any induced subgraph, then $\chi(G) \geq \chi(H)$. $\endgroup$ – Douglas S. Stones Nov 1 '12 at 21:12
2
$\begingroup$

Consider coloring such an induced subgraph, say $H$. Clearly, since $H = K_n$, you will needed $n$ colors to color $H$. However, $\chi(G) \geq \chi(H)$, because $G$ includes some other vertices and edges built on top of $H$. Hence, $\chi(G) \geq n$.

$\endgroup$
  • $\begingroup$ thanks for help.but that is not a proof although question is obvious. $\endgroup$ – World Nov 1 '12 at 20:31
  • 1
    $\begingroup$ @World Not sure how detailed you want the proof. If you ensist, consider a particular "least" coloring function of $G$, and note that it must color $H$ in at least $n$ colors, that would be more formal language but with the same idea. $\endgroup$ – gt6989b Nov 1 '12 at 20:34
  • $\begingroup$ Is it obvious that you need at least $n$ colours to properly colour $K_n$? (If you use fewer, than there are two adjacent vertices with the same colour.) Hence $\chi(K_n) \geq n$, which is all you need for the proof. $\endgroup$ – Douglas S. Stones Nov 1 '12 at 21:18

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.