Graph homomorphism to minor

Question

Is there a simple, finite, undirected graph $G=(V,E)$ with the following properties?

$\omega(G) < \chi(G)$ (where $\omega(G)$ is the size of the largest clique in $G$), and
up to isomorphism, the only proper minor $M$ of $G$ such that there is a graph homomorphism $f:G\to M$ is the complete graph $K_n$ where $n=\chi(G)$.

I apologize if there is an easy example to my question - could the person who downvoted my question (no offense taken of course!) give a hint to the example? Or maybe is the question unclear? I would be keen to make it better — Dominic van der Zypen, Sep 4 '16 at 12:27
I did not downvote, but it was probably because you meant to write proper minor instead of minor. Otherwise, since there is always a homomorphism from $G$ to $G$, your two conditions are clearly incompatible. — Tony Huynh, Sep 4 '16 at 14:07

Gordon Royle · Accepted Answer · 2016-09-04 12:59:31Z

5

I think a 5-cycle meets your needs.

Clique number 2, chromatic number 3. Check.

(It does have a homomorphism to itself, but I assume you meant proper minor.)

It has no homomorphism to a 4-cycle or a 4-path (the two possible minors with 4 edges) and so that leaves a hom to a triangle. Check.

answered Sep 4 '16 at 12:59

Gordon Royle

10.4k1 gold badge40 silver badges65 bronze badges

Add a comment |

1 Answer 1