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

DOI10.1016/J.JCTB.2020.04.002MaRDI QIDQ2200916zbMATH OpenOpenAlexFDO

Authors Meirun Chen, Reza Naserasr

Publication date 24 September 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2020.04.002

zbMATH Keywords

edge-coloringhomomorphismminorplanar graphstreewidth

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Homomorphism, automorphism and dualities in linear incidence geometry (51A10)

Review text

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.

Recommendations

• Homomorphisms and edge-colourings of planar graphs
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
• Oriented colorings of partial 2-trees
• Homomorphisms of 2-edge-colored graphs

Cites work

• Colouring series-parallel graphs
• Edge-colouring eight-regular planar graphs
• Edge-colouring seven-regular planar graphs
• Forbidden minors characterization of partial 3-trees
• Graph theory
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Homomorphisms and edge-colourings of planar graphs
• Homomorphisms of binary Cayley graphs
• Homomorphisms of planar signed graphs to signed projective cubes
• Homomorphisms of signed graphs
• Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• Mapping planar graphs into projective cubes
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On the chromatic number of cube-like graphs
• Optimal edge-colourings for a class of planar multigraphs
• Packing six \(T\)-joins in plane graphs
• Triple Transitive Graphs
• Walk-powers and homomorphism bounds of planar signed graphs

Cited in

(4)

• Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor
• High-girth cubic graphs are homomorphic to the Clebsch graph
• Extended double covers and homomorphism bounds of signed graphs
• Homomorphisms and edge-colourings of planar graphs

This page was built for publication: Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200916)