# Concepts of criticality in graph theory

A graph $G=(V,E)$ is said to be vertex-critical if removing a vertex $v\in V$ reduces the chromatic number $\chi(\cdot)$. Edge-criticality is defined in a similar manner. Moreover, $G$ is called contraction-critical if contracting any edge reduces the chromatic number.

Questions.

1) Are edge- and vertex-criticality equivalent?

2) What is an example of a graph $G$ such that $\omega(G) < \chi(G)$ [where $\omega(G)$ denotes the clique number), and $G$ is vertex-critical, but not contraction-critical?

• Taken literally, the answer to question 1) is no in view of an extremely small counterexample: the non-connected graph $\bullet\quad\bullet$ - $\bullet$ has $\chi=2$, is not vertex-critical (delete $\bullet$) but is edge-critical because deleting the edge makes $\chi$ drop from $2$ to $1$, and there is only this edge. – Peter Heinig May 29 '17 at 17:52

Concerning your first question, every edge-critical graph without isolated vertices must be vertex-critical, but not vice versa. For instance, the complement of a $7$-cycle is vertex-critical but not edge-critical.
Concerning your second question, every vertex-critical graph must be contraction-critical as well. Suppose we are contracting an edge $uv$ of a $k$-vertex-critical graph $G$. Since $G$ is $k$-vertex-critical, there is a $k$-colouring $c$ of $G$ in which $u$ is the only vertex coloured $k$. This is also a proper colouring of the graph with the edge $uv$ contracted.
• A correct statement is "every edge-critical graph without isolated vertices must be vertex-critical". Consider the minimal example $\bullet\ \bullet\text{-}\bullet$. Would you please edit-in this condition? – Peter Heinig May 30 '17 at 9:31
I think the graph studied in my article "16,051 formulas for Ottaviani's invariant of cubic threefolds" with Christian Ikenmeyer and Gordon Royle fits the bill. In the paper we considered a hypergraph on a set $V$ of 15 vertices where the hyperedges are 5-subsets of $V$. Let $G$ be the collinearity graph, namely the obtained by replacing each hyperedge by a complete graph $K_5$. See Section 4 of the article for an explicit description which shows that $\chi(G)=8$ while $\omega(G)=7$. This graph is vertex-critical and I suspect it is not contraction-critical but I did not check this last property.