Homomorphism bounds and edge-colourings of K4-minor-free graphs

We present a necessary and sufficient condition for a graph of odd-girth 2k+1 to bound the class of K4-minor-free graphs of odd-girth (at least) 2k+1, that is, to admit a homomorphism from any such K4-minor-free graph. This yields a polynomial-time algorithm to recognize such bounds. Using this condition, we first prove that every K4-minor free graph of odd-girth 2k+1 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 K(2k+1,k) satisfies the conditions, thus implying that every K4-minor free graph of odd-girth 2k+1 has fractional chromatic number exactly 2+1k. Knowing that a smallest bound of odd-girth 2k+1 must have at least (k+22) vertices, we build nearly optimal bounds of order 4k2. Furthermore, we conjecture that the suprema of the fractional and circular chromatic numbers for K4-minor-free graphs of odd-girth 2k+1 are achieved by a same bound of odd-girth 2k+1. If true, this improves, in the homomorphism order, earlier tight results on the circular chromatic number of K4-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 K4-minor-free multigraphs, we show that stronger results can be obtained in the case of K4-minor-free regular multigraphs.