Homomorphisms of partial t-trees and edge-coloring of partial 3-trees

A reformulation of the four-color theorem is to say that K 4 is the smallest graph to which every planar (loop-free) graph admits a homomorphism. Extending this theorem, the second author has proved (using the four-color theorem) that the Clebsch graph (a well known triangle-free graph on 16 vertices) is a smallest graph to which every triangle-free planar graph admits a homomorphism. As a further generalization he has proposed that the projective cube of dimension 2k, P C(2k), (that is the Cayley graph (Z 2k 2 , {e 1 , e 2 ,. .. , e 2k , J}, where e i 's are the standard basis and J = e 1 + e 2 + · · · + e 2k) is a smallest graph of odd-girth 2k +1 to which every planar graph of odd-girth at least 2k +1 admits a homomorphism. This conjecture is related to a conjecture of P. Seymour who claims that the fractional edge-chromatic number of a planar multigraph determines its edge-chromatic number (more precisely, Seymour conjectured that χ (G) = χ f (G) for any planar multigraph G). Note that the restriction of Seymour's conjecture on cubic (planar) graphs is Tait's reformulation of the four-color theorem. Both these conjectures are believed to be true for the larger class of K 5-minor-free graphs (which includes the class of planar graphs). Motivated by these conjectures and in extension of a recent work of L. Beaudou, F. Foucaud and the second author, which studies homomorphism bounds for the class of K 4-minor-free graphs, in this work we first give a necessary and sufficient condition for a graph B of odd-girth 2k + 1 to admit a homomorphism from any partial t-tree of odd-girth at least 2k + 1. Applying our results on the class of partial 3-trees, which is a rich subclass of K 5-minor-free graphs, we prove that P C(2k) is in fact a smallest graph of odd-girth 2k + 1 to which every partial 3-tree of odd-girth at least 2k + 1 admits a homomorphism. We then apply this result to show that every planar (2k + 1)-regular multigraph G whose dual is a partial 3-tree, and whose fractional edge-chromatic number is 2k + 1, is (2k + 1)-edge-colorable. Both these results are the best known supports for the general cases of the above mentioned conjectures in extension of the four-color theorem