2
$\begingroup$

We let $G$ be a graph which is $k$-color-critical, meaning $\chi (G) = k$ and removing any vertex results in a graph with a smaller chromatic number.

My attempt has been to suppose that the graph $G$ is disconnected. From here I would then say that $G$ has connected components $G_1,G_2,...,G_n.$ Since I am trying to do a proof by contradiction, I assume that in this case I should be able to remove a single vertex and either end up with a graph that is still $k$-colorable or a graph which has chromatic number $\chi (G-v) < k-1$ for some vertex $v$.

I have shown that if $G$ is $k$-color-critical then by removing a single vertex $v$ from $G$ we get $\chi (G-v)=k-1$.

I am not sure exactly what to do from here.

I am thinking something along the lines of the induced subgraphs $G_1,...,G_n$ and if $G$ is $k$-colorable then the max of the chromatic numbers of the subgraphs would be $k$.

$\endgroup$

2 Answers 2

3
$\begingroup$

Correct me if I'm wrong, but this might be an other way to prove the statement by contradiction:

Suppose your k-critical-colored $G$ graph is not connected, then $G$ must have at least two connected components, let's call them $G_1$ ... $G_n$ with $n \geq 2$.

You know that, as minimum, one of those connected components must be k-colored, otherwise your graph wouldn't be k-colored. We will call this connected component $G_1$. Now, grab a different connected component (for example $G_2$) and take away one of its vertex. Did $\chi(G)$ change? Not really, because we left $G_1$ untouched therefore $\chi(G_1)$ didn't change so neither did $\chi(G)$. However, we did remove a vertex from the graph and that contradicts the critical graph definition, that is, removing any vertex will result in a chromatic color decay.

We assumed $G$ wasn't connected and we stumbled upon a contradiction therefore $G$ must be connected.

$\endgroup$
2
$\begingroup$

Suppose we delete a vertex from $G_1$. The resulting graph is $(k-1)$-colorable, so in particular its subgraphs $G_2, G_3, \ldots, G_n$ are all $(k-1)$-colorable. But if instead we delete a vertex from $G_2$, we similarly get that $G_1$ is $(k-1)$-colorable. We can then combine our $(k-1)$-colorings of the components to get a $(k-1)$-coloring of $G$, contradicting our assumption that $\chi(G)=k$.

$\endgroup$
1
  • $\begingroup$ Got it. Start with $G_1$, kill a vertex, $G-v$ is $(k-1)$-colorable so all of the $G_2,...,G_n$ $(k-1)$-colorable. Then do process again $G_1$ $(k-1)$-colorable, so color all the connected components with $(k-1)$ colors so $G$ $(k-1)$ colorable, a contradiction. Thank you very much $\endgroup$
    – user43138
    Commented Dec 5, 2012 at 11:39

You must log in to answer this question.