Skip to main content
changed variable names in bullet point 2
Source Link

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$$\{a, b\}\in [V]^2\setminus E$ we have $\chi((V,E)) = \chi((V, (E\cup\{v,w\})))$$\chi((V,E)) = \chi((V, (E\cup\{a,b\})))$, that is, joining $v,w$ withadding an edge connecting $a$ and $b$ does not increase 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.

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 $\{a, b\}\in [V]^2\setminus E$ we have $\chi((V,E)) = \chi((V, (E\cup\{a,b\})))$, that is, adding an edge connecting $a$ and $b$ does not increase the chromatic number.
Source Link

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.