Search tip: add tags and a query to focus your search

By
kintali
on
Dec. 5, 2012

A random graph $G(n, \frac{1}{2})$ on $n$ vertices, is obtained by starting with a set of $n$ and adding every possible edge independently with probability $\frac{1}{2}$.

Hadwiger’s conjecture states that if an undirected simple graph $G$ has no $K_{t+1}$ minor then $G$ is $t$-colorable.

Prove that almost every $G(n, \frac{1}{2})$ graph satisfies Hadwiger’s conjecture.

[debug] activity: 100.0

By
kintali
on
Nov. 15, 2012
| Updated
on
May 19, 2013