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: 142.0

By
kintali
on
July 11, 2012
| Updated
on
Aug. 12, 2012

By
Chandra Chekuri
on
July 28, 2012
| Updated
on
July 28, 2012

By
kintali
on
June 29, 2012
| Updated
on
Oct. 19, 2012