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.

Let G be a graph with n vertices. Prove that the chromatic number of G is greater than or equal to its clique number. Also prove that the chromatic number is greater than or equal to (n/the adjacency number of G).

I know that in a clique any 2 vertices are adjacent, and that in a clique of 4 each vertex has a degree 3, so that we would need four different colors. So assuming a clique has n vertices we need n colors, so the clique number cannot be greater than the chromatic number, so it has to be less than or equal. Is that an adequate way to prove the first part?

For the second part, I am utterly confused about where to start this proof.

share|improve this question
    
Adjacency number is the number of the size of the largest independent set, its the number of vertices in the largest independent set in graph G –  Ali May 3 '12 at 0:49
    
In my book they use the symbol alpha, but I do not know how to type that. –  Ali May 3 '12 at 0:50
    
Your "adjacency number" is more commonly referred to as the "independence number" of a graph. –  Austin Mohr May 3 '12 at 0:55

1 Answer 1

up vote 3 down vote accepted

Your first proof looks good, but it can be stated more simply. If a graph contains a clique of size $k$, then at least $k$ colors are required to color just the clique. Thus, the chromatic number is at least $k$.

For the second part, work by contradiction. If you could color the graph $G$ with fewer than $n / \alpha(G)$ colors, then one of your color classes has size strictly larger than $\alpha(G)$ (why?). Since no two vertices within a color class are adjacent, that color class is itself an independent set of size strictly larger than $\alpha(G)$ - a contradiction.

share|improve this answer

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.