Is there a finite, connected, simple, undirected graph $G=(V,E)$ such that

- $G$ is not complete, and
- whenever two vertices of distance $2$ are identified ("folded"), then the chromatic number increases?

$\begingroup$
$\endgroup$

The answer is no.

We may assume $G$ is not complete. If $G$ is a cycle, then identifying any two vertices at distance 2 does not change the chromatic number. Now assume that $G$ is not a cycle. Consider a colouring of $G$ with $k:=\chi(G)$ colours. Let $v$ be a vertex of maximum degree $d$. By Brooks' Theorem, $k \leqslant d$. At most $k-1 \leqslant d-1$ colours appear on the neighbours of $v$. So there exists distinct neighbours $x,y$ of $v$ with the same colour. Identifying $x$ and $y$ produces a $k$-colourable graph. So the chromatic number has not increased.

Of course, this proof does not provide an efficient algorithm for finding the vertices at distance 2 to identify.

This proof is in the following references:

Curtis R. Cook and Anthony B. Evans. Graph folding. In Proc. 10th Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. XXIII–XXIV of Congress. Numer., pp. 305–314. Utilitas Math., 1979.

David R. Wood. Folding = Colouring, arxiv:0802.2467, 2008.

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

or