Skip to main content
1 of 2

The effects of collapsing vs joining non-adjacent vertices on the chromatic number

For any set $X$, let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$.

Is there a finite, simple, undirected, connected graph $G=(V,E)$ with the following properties?

  1. There is $\{v, w\}\in [V]^2\setminus E$ such that collapsing $v,w$ increases the chromatic number, but
  2. for all $\{v, w\}\in [V]^2\setminus E$ we have $\chi((V,E)) = \chi((V, (E\cup\{v,w\})))$, that is, joining $v,w$ with an edge does not increase the chromatic number.