Skip to main content
3 of 3
edited tags
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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?