Skip to main content
MathOverflow

Return to Question

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

This is a weakening of thatthat 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?

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?

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?

Source Link
Dominic van der Zypen
Dominic van der Zypen
  • 48.9k
  • 8
  • 47
  • 162

Contracting 2 edges

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?