6
$\begingroup$

Is there a simple undirected, connected, non-complete graph $G=(V,E)$ with at least $2$ edges, such that the following condition holds?

Whenever you contract $1$ or $2$ edges, the resulting graph has chromatic number strictly smaller than $\chi(G).$

EDIT: Added connectedness, otherwise $K_n$ plus an isolated point is an uninteresting solution for $n>2$.

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you allow triangles in your graph? If yes --- what happens to the edge $ac$ when you contract $ab$ and $bc$? Does it disappear or turn into a loop? $\endgroup$
    – Ilya Bogdanov
    Aug 18, 2016 at 11:19
  • 1
    $\begingroup$ @IlyaBogdanov When considering colouring problems, it is customary to suppress parallel edges and loops when taking minors. Note that if the chromatic number always goes down when we contract any number of edges, then the graph must be a complete graph (if Hadwiger's Conjecture is true). $\endgroup$
    – Tony Huynh
    Aug 18, 2016 at 11:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.