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.

Find the chromatic numbers of the following graphs:

  1. a graph $G_1$ obtained from $K_n$ by removing one edge
  2. a graph $G_2$ obtained from $K_n$ by removing two edges with a common vertex
  3. a graph $G_3$ obtained from $K_n$ by removing two edges without a common vertex.
share|improve this question
5  
Have you tried something? –  Karolis Juodelė Feb 4 '13 at 15:21
    
It seems like you have given this some thought. Have you been able to narrow the chromatic number down to a certain range? For instance, can you show that $G_1$ can be $(n-1)$-coloured, or that it can't be, say, $(n-3)$-coloured? Please share more details. –  Erick Wong Feb 4 '13 at 16:03
1  
Actually, K_n-1 is a part of G_1, so it can be n-1 colored, and that's a lower bound. It's obvious that an n-1 coloring exist, as we take the n-coloring of K_n and color the two vertices that shared that edge the same. So for G_1 the answer is n-1 –  tijme Feb 4 '13 at 16:09
1  
On the same note, $G_2$ is a part of $G_1$ and $K_{n-1}$ is a part of $G_2$ (remove the shared vertex). Thus, it should also have chromatic number n-1 –  tijme Feb 4 '13 at 16:19
1  
We can find the copy of $K_{n-2}$ easily (take a vertex from each edge). We can find an n-2 coloring for $G_3$ from $G_1$ the same way we found one for $G_1$ from $K_n$ –  tijme Feb 4 '13 at 16:25

1 Answer 1

  1. $K_n-1$ is a part of $G_1$, so it can be $n-1$ colored, and that's a lower bound. It's obvious that an $n-1$ coloring exist, as we take the n-coloring of $K_n$ and color the two vertices that shared that edge the same. So for $G_1$ the answer is $n-1$
  2. $G_2$ is a part of $G_1$ and $K_{n−1}$ is a part of $G_2$ (remove the shared vertex). Thus, it should also have chromatic number $n-1$
  3. $G_3$ contains $K_{n−2}$ (take a vertex from each edge). We can find an $n-2$ coloring for $G_3$ from $G_1$ the same way we found one for $G_1$ from $K_n$
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.