-3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 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
    Commented May 29, 2017 at 17:52

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented May 30, 2017 at 9:31
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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