# Chromatic Numbers for Graphs

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