?
Homomorphism bounds and edge-colourings of K4-minor-free graphs
We present a necessary and sufficient condition for a graph of odd-girth to bound the class of -minor-free graphs of odd-girth (at least) , that is, to admit a homomorphism from any such -minor-free graph. This yields a polynomial-time algorithm to recognize such bounds. Using this condition, we first prove that every -minor free graph of odd-girth admits a homomorphism to the projective hypercube of dimension 2k. This supports a conjecture of the third author which generalizes the four-colour theorem and relates to several outstanding conjectures such as Seymour's conjecture on edge-colourings of planar graphs. Strengthening this result, we show that the Kneser graph satisfies the conditions, thus implying that every -minor free graph of odd-girth has fractional chromatic number exactly . Knowing that a smallest bound of odd-girth must have at least vertices, we build nearly optimal bounds of order . Furthermore, we conjecture that the suprema of the fractional and circular chromatic numbers for -minor-free graphs of odd-girth are achieved by a same bound of odd-girth . If true, this improves, in the homomorphism order, earlier tight results on the circular chromatic number of -minor-free graphs. We support our conjecture by proving it for the first few cases. Finally, as an application of our work, and after noting that Seymour provided a formula for calculating the edge-chromatic number of -minor-free multigraphs, we show that stronger results can be obtained in the case of -minor-free regular multigraphs.