0
$\begingroup$

A graph is called color-critical provided each subgraph obtained by removing a vertex has a smaller chromatic number. Let $G=(V,E)$ be a color-critical graph. Prove that $G$ does not have an articulation set $U$ such that $G_U$ is a complete graph.

My approach to this problem has been to use contradiction. Suppose there exists an articulation $U$ such that $G_U$ is a complete graph say on $t$ vertices. Then the graph $G_{V-U}$ is a disconnected graph with components $G_1,G_2,...,G_m$ ,$m\geq 2.$ The graph $G_U$ is $t$ colorable since it is a complete graph, whereas the components are at most $k-1$ colorable, where $k=\chi(G)$. I think that the goal would be to find a coloring that is less than $k$ for the entire graph to obtain a contradiction, but I am not sure how to proceed. Any hints will be much appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

Hint: Consider the graphs $G_i \cup G_U$. How many colors does it take to color those graphs? Can you combine those colorings to get a coloring of the entire graph?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .