3
$\begingroup$

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.
$\endgroup$
4
$\begingroup$

Yes, such a graph does exist. Let $G$ be obtained from the complete graph $K_{100}$ by adding two non-adjacent vertices $v$ and $w$ such that $|N_G(v)|=|N_G(w)|=50$ and $N_G(v) \cup N_G(w)=V(K_{100})$. Here, $N_G(v)$ denotes the set of vertices of $G$ which are adjacent to $v$. Then collapsing $v$ and $w$ in $G$ yields $K_{101}$, which increases the chromatic number. On the other hand, it is easy to see that adding any edge to $G$ does not increase the chromatic number.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Here $50$ can be treated as a variable, whose smallest value seems to be $2$. Bigger values of $50$ have the advantage that you can add quite a few edges without increasing the chromatic number. $\endgroup$ – Andreas Blass May 19 at 16:25
  • $\begingroup$ @AndreasBlass Indeed. We can even allow $N_G(v)$ and $N_G(w)$ to intersect if we like. Most values of $|N_G(v)|, |N_G(w)|$, and $|N_G(v) \cap N_G(w)|$ will give valid examples (this is basically a list colouring problem on $v$ and $w$). $\endgroup$ – Tony Huynh May 20 at 6:09
  • $\begingroup$ Beautiful example, thanks @TonyHuynh! $\endgroup$ – Dominic van der Zypen May 20 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.