0
$\begingroup$

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

closed as off-topic by user21820, ℋolo, Arnaud D., Jendrik Stelzner, Namaste Sep 11 '18 at 15:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, ℋolo, Arnaud D., Jendrik Stelzner, Namaste
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ Have you tried something? $\endgroup$ – Karolis Juodelė Feb 4 '13 at 15:21
  • $\begingroup$ 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. $\endgroup$ – Erick Wong Feb 4 '13 at 16:03
  • 1
    $\begingroup$ 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 $\endgroup$ – tijme Feb 4 '13 at 16:09
  • 1
    $\begingroup$ 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 $\endgroup$ – tijme Feb 4 '13 at 16:19
  • 1
    $\begingroup$ 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$ $\endgroup$ – tijme Feb 4 '13 at 16:25
4
$\begingroup$
  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$
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.