Graph such that edge contraction increases chromatic number

Question

Let $G=(V,E)$ be a simple, undirected graph with the following properties:

1. Contracting any edge increases the chromatic number by $1$;
2. For each minor $M$ of $G$ we have $\chi(M) \leq \chi(G) + 1$.

Does it follow that $G$ is isomophic to $C_{2n}$ (the circle on $2n$ points) for some $n\in\mathbb{N}$?

Answer 1

Any bridgeless bipartite outerplanar graph has the properties you describe, since:

• Contracting any edge will introduce an odd cycle;
• Outerplanar graphs are a minor-closed family and are all 3-colourable.

In particular, cycles of even length are special cases of bridgeless bipartite outerplanar graphs.