4
$\begingroup$

Show that a k-critical graph is connected. Furthermore, show that it does not have a vertex whose removal disconnects the graph (such a vertex is known as a cut vertex).

I have managed to proove , I think, the first part Let's assume G is not connected. Since χ(G) = k, (If G1,G2,...,Gr are the components of a disconnected graph G, then χ(G) = max χ(Gi) 1≤i≤r ) then there is a component G1 of G such that χ(G1)=k.If v is any vertex of G which is not in G1,then G1 isa component of the subgraph G − v. Therefore, χ (G − v) = χ (G1 ) = k. This contradicts the fact that G is k-critical. Hence G is connected.

But I can't manage to prove the second part..ie that there is not cut vertex. Anyone can help?

$\endgroup$
5
$\begingroup$

Your statement is a special case of more general theorem I was researching when I came across your question:

T: Cut in a $k$-critical graph is not clique.

Proof: Assume that cut $S$ in $k$-critical graph $G=(V,E)$ is clique. Components of $G \setminus S$ are $\{C_1 \dots C_r\}$. For each subgraph of $G$ in the form of $C_i\cup S$, find total coloring $\phi_i$ with $k-1$ or less colors. Let $\{v_i \dots v_m\}$ be vertices of $S$ that have different colors in the coloring $\phi_i$. Now because $S$ is clique, you can permute the colors on $v_1 \dots v_m$ in such a way that $\phi_i(v_j)=j$. Finally, you unite all the colorings $\phi_1 \dots \phi_r$, thus getting total coloring on $G$ with only $k-1$ colors. This contradicts the $k$-criticality of $G$ and proves the theorem.

Because single vertex is a clique in every graph, your statement is proven.

PS: how is resurrecting of old threads looked upon in these parts?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome to MSE! If you feel that you have something new to contribute to an old thread, this is absolutely fine. Similarly to you, someone else might look for an answer later, and will find what you added. For future submissions, you might find this summary of MathJax helpful: meta.math.stackexchange.com/questions/5020/… $\endgroup$ – gnometorule Feb 14 '13 at 17:46
  • $\begingroup$ I was missinng such reference exactly when writing this up! Thanks! $\endgroup$ – BoZenKhaa Feb 14 '13 at 18:10
2
$\begingroup$

Recall that "critical" also means that you cannot remove an edge without reducing the chromatic number of the graph.

If G had a cut vertex you could remove an edge adjacent to that vertex without decreasing $\chi(G)$.

I hope this suffices as a hint.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy