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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ No, consider an cycle. $\endgroup$– Brendan McKayOct 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$– ArnaudOct 7, 2015 at 9:17
Add a comment
|