3
$\begingroup$

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) <k$ 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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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:

enter image description here

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

$\endgroup$
3
  • $\begingroup$ That means to show that a graph is k-critical one must show it is both k-vertex critical and k-edge critical - right ? $\endgroup$
    – Megha
    Commented Feb 1, 2021 at 15:52
  • $\begingroup$ 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. $\endgroup$ Commented Feb 1, 2021 at 16:00
  • $\begingroup$ Okay. Thank You. $\endgroup$
    – Megha
    Commented Feb 1, 2021 at 16:57

You must log in to answer this question.

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