Triangle decompositions of planar graphs

DOI10.7151/DMGT.1882zbMATH Open1339.05078arXiv1504.00617OpenAlexW2964188778MaRDI QIDQ726643FDOQ726643

C. M. van Bommel, Christina M. Mynhardt

Publication date: 13 July 2016

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• A note on edge-decompositions of planar graphs
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Decomposing a planar graph with girth at least 8 into a forest and a matching
• Planar graphs decomposable into a forest and a matching
• The NP-Completeness of Some Edge-Partition Problems
• 3K2-decomposition of a graph
• T. P. Kirkman, Mathematician
• Edge decompositions of multigraphs into 3-matchings
• Fractional Triangle Decompositions in Graphs with Large Minimum Degree
• Title not available (Why is that?)
• Edge-decompositions of graphs with high minimum degree

Cited In (6)

• Decompositions of triangle-dense graphs
• Vertical decompositions for triangles in 3-space
• Gallai's path decomposition conjecture for triangle-free planar graphs
• Title not available (Why is that?)
• Triangle edge deletion on planar glasses-free RGB-digraphs
• On triangles in derangement 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)