For any set $X$, we let $[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$.

If $G=(V,E)$ is a simple, undirected graph, and $v\in V$, let $N(v) = \{z\in V: \{v,z\}\in E\}$. Given any $v\in V$, we use the following notation:

  1. Let $G\setminus\{v\} := (V\setminus \{v\}, E \cap [V\setminus\{v\}]^2)$, and
  2. if $w\in V$ with $\{v,w\}\in E$, let $(G\setminus\{v\})^w := (V\setminus\{v\}, E_{v,w})$ where $E_{v,w}:= (E \cap [V\setminus\{v\}]^2) \cup \{\{w,z\}: z\in N(v)\}$.

A graph $G=(V,E)$ is said to be vertex-critical if $\chi(G\setminus\{v\}) < \chi(G)$ for every $v\in V$. We say $G$ is collapse-critical if $\chi\big((G\setminus\{v\})^w\big) < \chi(G)$ for all $v\in V$ and $w\in V$ such that $\{v,w\}\in E$. It is clear that $\chi(G\setminus\{v\})\leq \chi\big((G\setminus\{v\})^w\big)$, so collapse-criticality implies vertex-criticality.

Question. What is an example of a finite, connected graph that is vertex-critical, but not collapse-critical?

  • 1
    $\begingroup$ The only vertex critical graph $G$ with $\chi(G)=3$ is the cycle graph of odd length, but cycle graphs of odd length at least 5 are never collapse critical. $\endgroup$ Commented Sep 20, 2021 at 14:20
  • 1
    $\begingroup$ For problems like this, it would be good to use or write some code that tests random graphs for vertex criticality and edge criticality. Testing whether a graph is bipartite can be done in linear time. Computing the chromatic number of a graph is more difficult, but one can write a backtracking algorithm that traverses through all (up-to-renaming the colors) partial $k$-colorings $f:\{v_{1},\dots,v_{r}\}\rightarrow[k]$ of your graph $(V,E)$ with $V=\{v_{1},\dots,v_{n}\}$. $\endgroup$ Commented Sep 20, 2021 at 14:28
  • 1
    $\begingroup$ Also, the direction of the inequality between $\chi((G\setminus\{v\})^{w})$ and $\chi(G\setminus\{v\})$ seems to have been reversed. $\endgroup$ Commented Sep 20, 2021 at 14:30
  • $\begingroup$ If you want to test vertex critical graphs $G$ with $\chi(G)>3$, then it is easy to estimate the time it takes for your backtracking algorithm to terminate and compute the chromatic number of your graphs; this will save you some time so you can just compute the most efficient backtrackings. See the paper 'Estimating the Efficiency of Backtrack Programs' by Donald E. Knuth. $\endgroup$ Commented Sep 20, 2021 at 14:57
  • $\begingroup$ Thanks @JosephVanName - indeed I got the inequality of collapse-criticality vs vertex-criticality wrong. Will think about your other points and try some random graphs. $\endgroup$ Commented Sep 20, 2021 at 15:41

1 Answer 1


Unless I'm mistaken, your definition of $(G\setminus \{v\})^w$ is symmetrical, and generally referred as an edge-contraction, so collapse critical is the same as edge-contraction critical.

this graph is vertex-critical, but not collapse-critical.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.