Triangle Decompositions of Planar Graphs

Christina M. Mynhardt; Christopher M. van Bommel

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 643-659
  • ISSN: 2083-5892

Abstract

top
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 K4 as underlying graph, we give necessary and sufficient conditions on the multiplicities of its edges for G to be triangle and rationally triangle decomposable.

How to cite

top

Christina M. Mynhardt, and Christopher M. van Bommel. "Triangle Decompositions of Planar Graphs." Discussiones Mathematicae Graph Theory 36.3 (2016): 643-659. <http://eudml.org/doc/285621>.

@article{ChristinaM2016,
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 K4 as underlying graph, we give necessary and sufficient conditions on the multiplicities of its edges for G to be triangle and rationally triangle decomposable.},
author = {Christina M. Mynhardt, Christopher M. van Bommel},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graphs; triangle decompositions; rational triangle decompositions},
language = {eng},
number = {3},
pages = {643-659},
title = {Triangle Decompositions of Planar Graphs},
url = {http://eudml.org/doc/285621},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Christina M. Mynhardt
AU - Christopher M. van Bommel
TI - Triangle Decompositions of Planar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 643
EP - 659
AB - 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 K4 as underlying graph, we give necessary and sufficient conditions on the multiplicities of its edges for G to be triangle and rationally triangle decomposable.
LA - eng
KW - planar graphs; triangle decompositions; rational triangle decompositions
UR - http://eudml.org/doc/285621
ER -

References

top
  1. [1] B. Barber, D. Kühn, A. Lo and D. Osthus, Edge-decompositions of graphs with high minimum degree, arXiv:1410.5750v3, 2015. Zbl1346.05224
  2. [2] A. Bialostocki and Y. Roditty, 3K2-decomposition of a graph, Acta Math. Acad. Sci. Hungar. 40 (1982) 201-208. doi:10.1007/BF01903577[Crossref] 
  3. [3] N.L. Biggs, T.P. Kirkman, Mathematician, Bull. Lond. Math. Soc. 13 (1981) 97-120. doi:10.1112/blms/13.2.97[Crossref] 
  4. [4] O. Borodin, A.O. Ivanova, A. Kostochka and N.N. Sheikh, Planar graphs decompos- able into a forest and a matching, Discrete Math. 309 (2009) 277-279. doi:10.1016/j.disc.2007.12.104[Crossref] Zbl1221.05070
  5. [5] F. Dross, Fractional triangle decompositions in graphs with large minimum degree, arXiv:1503.08191v3, 2015.[WoS] 
  6. [6] O. Favaron, Z. Lonc and M. Truszczyński, Decompositions of graphs into graphs with three edges, Ars Combin. 20 (1985) 125-146. Zbl0604.05028
  7. [7] K. Garaschuk, Linear Methods for Rational Triangle Decompositions, Doctoral Dissertation (University of Victoria, 2014). http://hdl.handle.net/1828/5665 
  8. [8] Z. Lonc, M. Meszka and Z. Skupień, Edge decompositions of multigraphs into 3- matchings, Graphs Combin. 20 (2004) 507-515. doi:10.1007/s00373-004-0581-0[Crossref] Zbl1053.05102
  9. [9] R. Häggkvist and R. Johansson, A note on edge-decompositions of planar graphs, Discrete Math. 283 (2004) 263-266. doi:10.1016/j.disc.2003.11.017[Crossref] Zbl1042.05083
  10. [10] I. Holyer, The NP-completeness of some edge-partition problems, SIAM J. Comput. 10 (1981) 713-717. doi:10.1137/0210054[Crossref] Zbl0468.68069
  11. [11] P. Keevash, The existence of designs, arXiv:1401.3665v1, 2014. 
  12. [12] S.-J. Kim, A.V. Kostochka, D.B. West, H. Wu and X. Zhu, Decomposition of sparse graphs into forests and a graph with bounded degree, J. Graph Theory 74 (2013) 369-391. doi:10.1002/jgt.21711[Crossref] 
  13. [13] T. Kirkman, On a problem in combinations, The Cambridge and Dublin Mathematical Journal (Macmillan, Barclay, and Macmillan) II (1847) 191-204. 
  14. [14] C.St.J.A. Nash-Williams, An unsolved problem concerning decomposition of graphs into triangles, in: P. Erds, P. Rnyi and V.T. S´os (Eds.), Combinatorial Theory and its Applications III (North Holland, 1970) 1179-1183. 
  15. [15] J. Steiner, Combinatorische Aufgaben, J. Reine Angew. Math. 45 (1853) 181-182. doi:10.1515/crll.1853.45.181[Crossref] 
  16. [16] Y. Wang and Q. Zhang, Decomposing a planar graph with girth at least 8 into a forest and a matching, Discrete Math. 311 (2011) 844-849. doi:10.1016/j.disc.2011.01.019 [Crossref][WoS] 
  17. [17] D.B. West, Introduction to Graph Theory (Prentice Hall, Inc., Upper Saddle River, NJ, 1996). Zbl0845.05001
  18. [18] W.S.B. Woolhouse, Prize question #1733, Lady’s and Gentleman’s Diary (1844) London, Company of Stationers. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.