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.


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?

  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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