0
$\begingroup$

A finite, simple, undirected graph $G=(V,E)$ is said to be vertex-critical if for all $v\in V$ we have $\chi(G\setminus \{v\}) < \chi(G)$. Similarly, we call it edge critical, if removing any edge reduces the chromatic number, and edge-contraction critical if contracting any edge reduces $\chi(\cdot)$.

What are the implications between these 3 kinds of criticality? I would especially be happy for examples that show that a certain criticality does not imply one of the other kinds.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

It is quite easy to show edge-contraction critical <=> edge critical - just expand the definitions to construct a suitable coloring. (For the reverse direction note that if we delete the edge to be contracted, the coloring given by edge criticality must give the endpoints the same color, else it would give a proper coloring if the original graph.)

It is also easy to show edge critical + no isolated vertices => vertex critical. With isolated vertices there are counterexamples such as $K_2$ + an isolated vertex.

Vertex critical but not edge critical: Vertex critical graph with at least one non critical edge.

$\endgroup$

You must log in to answer this question.

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