Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees (Q2200916)

The paper extends the notion of odd-girth to weighted graphs, and provides some classifications. It gives a necessary and sufficient condition for a graph of odd-girth $2k+1$ to bound all partial \(t\)-trees of odd-girth at least $2k+1$, and finds an optimal bound of odd-girth $2k + 1$ for partial 3-trees of odd-girth at least $2k + 1$. 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, it is shown that the Clebsch graph (a well-known triangle-free graph on 16 vertices) is the smallest graph to which every triangle-free planar graph admits a homomorphism. The paper also gives a necessary and sufficient condition for a graph of odd-girth $2k + 1$ to admit a homomorphism from any partial \(t\)-tree of odd-girth at least $2k + 1$. Finally, it is shown that every planar $(2k + 1)$-regular multigraph, whose dual is a partial 3-tree and whose fractional edge chromatic number is $2k + 1$, is $(2k + 1)$-edge-colorable.