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.