Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
More generally, if $H$ is any induced subgraph, then $\chi(G) \geq \chi(H)$. –  Douglas S. Stones Nov 1 '12 at 21:12
add comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
thanks for help.but that is not a proof although question is obvious. –  World Nov 1 '12 at 20:31
    
@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. –  gt6989b Nov 1 '12 at 20:34
    
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. –  Douglas S. Stones Nov 1 '12 at 21:18
add comment

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.