Skip to main content
2 of 3
edited tags
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Chromatic number and vertex connectivity

A conjecture of Mader implies that for any positive integer $n\geq2$, every graph with average degree at least $3n-4$ contains an $n$-connected subgraph. Mader himself proved this for $n=2,3,4,5,6,7$. In particular, any graph with minimum degree $5$ admits a $3$-connected subgraph, and so any graph with chromatic number at least $6$ admits a $3$-connected subgraph.

Question: Does every graph with chromatic number $5$ already admit a $3$-connected subgraph?