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
    Commented 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
    Commented Aug 18, 2016 at 11:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .