On the odd-minor variant of Hadwiger's conjecture

A {\it $K_l$ -expansion} consists of $l$ vertex-disjoint trees, every two of which are joined by an edge. We call such an expansion {\it odd} if its vertices can be two-coloured so that the edges of the trees are bichromatic but the edges between trees are monochromatic. We show that, for every $l$, if a graph contains no odd $K_l$ -expansion then its chromatic number is $O(l \sqrt{\log l})$. In doing so, we obtain a characterization of graphs which contain no odd $K_l$ -expansion which is of independent interest. We 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$. Finally, we discuss the algorithmic implications of these results.