W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Odd Hadwiger's Conjecture
December 7, 2012
2pm - 3pm
We say that a graph G has an odd clique minor of order at least t if there are t vertex disjoint trees in G such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic.
Odd Hadwiger's Conjecture states that if a graph G has chromatic number t, then G contains an odd clique minor of size t. This is substantially stronger than the well-known Hadwiger's Conjecture.
In this talk we will survey recent progress on Odd Hadwiger's Conjecture. In particular, let G be a
graph with n vertices and alpha(G) = 2. We prove that G contains an odd clique minor of size ceiling of n/2 if omega(G) is greater than or equal to n/4, and of size (2omega(G)+n)/3 otherwise.
Odd Hadwiger's Conjecture states that if a graph G has chromatic number t, then G contains an odd clique minor of size t. This is substantially stronger than the well-known Hadwiger's Conjecture.
In this talk we will survey recent progress on Odd Hadwiger's Conjecture. In particular, let G be a
graph with n vertices and alpha(G) = 2. We prove that G contains an odd clique minor of size ceiling of n/2 if omega(G) is greater than or equal to n/4, and of size (2omega(G)+n)/3 otherwise.