Triangle decompositions of planar graphs

DOI10.7151/DMGT.1882MaRDI QIDQ726643zbMATHOpenAlexFDO

Authors Christina M. Mynhardt, C. M. van Bommel

Publication date 13 July 2016

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.00617

zbMATH Keywords

planar graphsrational triangle decompositionstriangle decompositions

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A multigraph G is triangle decomposable if its edge set can be partitioned into subsets, each of which induces a triangle of G, and rationally triangle decomposable if its triangles can be assigned rational weights such that for each edge e of G, the sum of the weights of the triangles that contain e equals 1. We present a necessary and sufficient condition for a planar multigraph to be triangle decomposable. We also show that if a simple planar graph is rationally triangle decomposable, then it has such a decomposition using only weights 0,1 and 1/2. This result provides a characterization of rationally triangle decomposable simple planar graphs. Finally, if G is a multigraph with the complete graph of order 4 as underlying graph, we give necessary and sufficient conditions on the multiplicities of its edges for G to be triangle and rationally triangle decomposable.

Recommendations

• Triangle decompositions of \(\lambda K_v - \lambda K_w - \lambda K_u\)
• Triangle-partitioning edges of planar graphs, toroidal graphs and \(k\)-planar graphs
• Fractional triangle decompositions in graphs with large minimum degree
• scientific article; zbMATH DE number 2024685
• Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph

Cites work

• scientific article; zbMATH DE number 3974987 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• 3K2-decomposition of a graph
• A note on edge-decompositions of planar graphs
• Decomposing a planar graph with girth at least 8 into a forest and a matching
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Edge decompositions of multigraphs into 3-matchings
• Edge-decompositions of graphs with high minimum degree
• Fractional triangle decompositions in graphs with large minimum degree
• Planar graphs decomposable into a forest and a matching
• T. P. Kirkman, Mathematician
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(5)

• Vertical decompositions for triangles in 3-space
• On triangles in derangement graphs
• scientific article; zbMATH DE number 2192094 (Why is no real title available?)
• Triangle edge deletion on planar glasses-free RGB-digraphs
• Gallai's path decomposition conjecture for triangle-free planar graphs

This page was built for publication: Triangle decompositions of planar graphs

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