Fractional coloring and the odd Hadwiger’s conjecture

Gerards and Seymour (see [T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley-Interscience, 1995], page 115) conjectured that if a graph has no odd complete minor of order pp, then it is (p−1)(p−1)-colorable. This is an analogue of the well known conjecture of Hadwiger, and in fact, this would immediately imply Hadwiger’s conjecture. The current best known bound for the chromatic number of graphs without an odd complete minor of order pp is O(plogp) by the recent result by Geelen et al. [J. Geelen, B. Gerards, B. Reed, P. Seymour, A. Vetta, On the odd variant of Hadwiger’s conjecture (submitted for publication)], and by Kawarabayashi [K. Kawarabayashi, Note on coloring graphs without odd KkKk-minors (submitted for publication)] (but later). But, it seems very hard to improve this bound since this would also improve the current best known bound for the chromatic number of graphs without a complete minor of order pp.Motivated by this problem, we prove that the “fractional chromatic number” of a graph GG without odd KpKp-minor is at most 2p2p; that is, it is possible to assign a rational q(S)≥0q(S)≥0 to every stable set S⊆V(G)S⊆V(G) so that ∑S∋vq(S)=1∑S∋vq(S)=1 for every vertex vv, and ∑Sq(S)≤2p∑Sq(S)≤2p.This generalizes the result of Reed and Seymour [B. Reed, P.D. Seymour, Fractional chromatic number and Hadwiger’s conjecture, J. Combin. Theory Ser. B 74 (1998) 147–152] who proved that the fractional chromatic number of a graph with no Kp+1Kp+1-minor is at most 2p2p.