A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor (Q2151177): Difference between revisions

Given graphs \(G\) and \(H\), we say \(G\) has an \(H\) minor if a graph isomorphic to \(H\) can be obtained from a subgraph \(G^{\prime}\) of \(G\) by contracting edges. The famous Hadwiger conjecture states that if \(G\) has no \(K_{t}\) minor it is \((t-1)\)-colourable. This is known for \(t\leq 6\), and approximate results are also known, a recent one being the result of \textit{L Postle} [``An even better density increment theorem and its application to Hadwiger's conjecture'', Preprint, \url{arXiv:2006.14945}] that every graph with no \(K_{t}\) minor is properly \(O (t(\log\log(t))^{6})\) colourable.\par Again given graphs \(G\) and \(H\), we say that \(G\) has an odd \(H\) minor if it has an \(H\) minor in which the set of contracted edges forms a cut in \(G^{\prime}\). Gerards and Seymour made the (substantial) generalisation of Hadwiger's conjecture that if \(G\) has no odd \(K_{t}\) minor then it is properly \(t\)-colourable. The aim of the paper under review is to show that if \(G\) has no odd \(K_t\) minor then, for every \(\beta>1/4\), it is properly \(O (t(\log(t))^{\beta})\) colourable. (A similar result had been proved, when we do not insist that the minor is an odd minor, by Postle in his work towards the above result.) \par Since the paper under review was published, \textit{L. Postle} [``Further progress towards the list and odd versions of Hadwiger's conjecture'', Preprint, \url{arXiv:2010.05999}] has produced another preprint in which he shows that if \(G\) has no odd \(K_{t}\) minor it is properly \(O (t(\log\log(t))^{6})\) colourable. \par Proof techniques in the paper under review are similar to those of an earlier paper of the authors where they first broke the ``degeneracy bound'', but parts of the argument are harder as a reduction to the case of high connectivity cannot be used as easily as in the previous paper.