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.
Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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
    Commented May 19, 2020 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
    Commented May 20, 2020 at 6:09
  • $\begingroup$ Beautiful example, thanks @TonyHuynh! $\endgroup$
    – Dominic van der Zypen
    Commented May 20, 2020 at 7:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .