-2
$\begingroup$

Let $G = (V,E)$ be a finite, simple, undirected, connected graph, such that contracting an edge reduces the chromatic number. Does this imply that $G$ is complete?

$\endgroup$
2
  • 1
    $\begingroup$ No, consider an cycle. $\endgroup$ Oct 7, 2015 at 9:09
  • 4
    $\begingroup$ The graphs you are considering are called contraction-critical k-chromatic graphs. There is some literature on the topic, see for example "A contraction theorem for abstract graphs" of Dirac. $\endgroup$
    – Arnaud
    Oct 7, 2015 at 9:17

1 Answer 1

2
$\begingroup$

Any odd cycle of length at least 5 is a counterexample.

$\endgroup$

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