## May 28, Spring Quarter 2010: Theory Seminar

### 1:00pm in ICS 243

#
On the odd-minor variant of Hadwiger's conjecture

##
Nicolaos Matsakis

Presenting a paper by
Jim Geelen, Bert Gerards, Bruce Reed, Paul Seymour, Adrian Vetta,
from the Journal of Combinatorial Theory, Series B(99) 1: 20-29,
2009.

Abstract:
This paper deals with the odd-minor variant of the one of the most
well known open problems in Graph Theory, the conjecture of Hugo
Hadwiger, which states that the chromatic number of every graph is
less or equal than the number of vertices of its largest clique
minor. More specifically, a K_{l}-expansion consists of l
vertex-disjoint trees, every two of which are joined by an edge. We
call such an expansion odd if its vertices can be two-coloured, so
that the edges of the trees are bichromatic, but the edges between
trees are monochromatic. In this paper, the authors show that, for
every l, if a graph contains no odd K_{l}-expansion then its
chromatic number is O(l\sqrt{logl}). In doing so, they obtain a
characterization of graphs which contain no odd K_{l}-expansion.
They, also, prove that, given a graph and a subset S of its vertex
set, either there are k vertex-disjoint odd paths with endpoints in
S, or there is a set X of at most 2k-2 vertices such that every odd
path with both ends in S contains a vertex in X. Some algorithmic
implications of this result are also discussed.