1
$\begingroup$

This is a weakening of that question.

Let $G=(V,E)$ be a simple, undirected, connected graph, let $n=|V|$ and assume $n\geq 3$. Suppose that whenever you contract $2$ edges, the chromatic number decreases.

Does this imply that $G$ contains a clique of $n-1$ vertices?

Improve this question
$\endgroup$
2
  • $\begingroup$ Something interesting I noticed, not sure if it helps: A graph has a clique of $n - 1$ vertices if and only if its complement has no two edges without vertices in common and no triangles. For a graph as you describe, any subgraph given by removing a triangle or by removing two edges without vertices in common must also have decreased chromatic number. $\endgroup$
    – user44191
    Commented Aug 20, 2016 at 2:01
  • $\begingroup$ Interesting comment, thank you! I don't quite see yet how to use this for answering the question, but maybe there is a way. $\endgroup$
    – Dominic van der Zypen
    Commented Aug 20, 2016 at 12:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .