0
$\begingroup$

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

  1. $\omega(G) < \chi(G)$ (where $\omega(G)$ is the size of the largest clique in $G$), and
  2. 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)$.
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Dominic van der Zypen Sep 4 '16 at 12:27
  • $\begingroup$ 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. $\endgroup$ – Tony Huynh Sep 4 '16 at 14:07
5
$\begingroup$

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.

$\endgroup$

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.