# Query regarding $k$-critical graphs

I am studying coloring of graphs and having some basic doubts in the theorems regarding $$k$$-critical graph.

$$\mathbf {Definition}$$ - A graph $$G$$ is said to be $$k$$-critical if $$\chi (G) = k$$ and $$\chi(H) < k$$ for any proper subgraph $$H$$ of $$G$$.

Now all the theorems regarding $$k$$-critical graphs use the fact that – if $$\chi(G) =k$$ and $$\chi(G \setminus v) for any vertex $$v$$ of $$G$$ , then $$G$$ is $$k$$-critical.

But I am not understanding how the above statement is equivalent to the definition. Because there may exist a proper subgraph $$H$$ of $$G$$ that has all the vertices of $$G$$. This may be very trivial but I am really struggling with this. Someone please help me to understand this.

Thank You.

You are right and the people stating those theorems are (a little bit) wrong.

Unfortunately, many people talk about $$k$$-critical graphs when they really mean "$$k$$-vertex-critical". A $$k$$-vertex-critical graph is exactly one for which deleting any vertex reduces the chromatic number. Equivalently, any proper induced subgraph has a smaller chromatic number.

Just to make sure what you are saying is always clear, I would avoid using the term "$$k$$-critical graph" and only ever talk about "$$k$$-vertex-critical" and "$$k$$-edge-critical" graphs. Then it's clear that the second kind of graph really is sensitive to the removal of a single edge.

To reassure you that there really is a difference, consider the following graph, taken from the paper Efficient algorithms for finding critical subgraphs by Desrosiers, Galinier, and Hertz:

This graph has chromatic number $$4$$, and will continue to have chromatic number $$4$$ if the edge $$v_1v_2$$ is deleted, but if you delete any vertex, the result has chromatic number $$3$$.

• That means to show that a graph is k-critical one must show it is both k-vertex critical and k-edge critical - right ? Commented Feb 1, 2021 at 15:52
• No, $k$-edge-critical implies $k$-vertex-critical, unless there are isolated vertices. If deleting an edge changes the chromatic number, then deleting either of its endpoints changes the chromatic number, too. (A valid coloring of $G$ without the edge $vw$ gives us a coloring of $G-v$ and of $G-w$.) So if deleting any edge changes the chromatic number, and every vertex is the endpoint of some edges, then deleting any vertex changes the chromatic number. Commented Feb 1, 2021 at 16:00
• Okay. Thank You. Commented Feb 1, 2021 at 16:57