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.
@article{bwmeta1.element.doi-10_7151_dmgt_1882,
author = {Christina M. Mynhardt and Christopher M. van Bommel},
title = {Triangle Decompositions of Planar Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {643-659},
zbl = {1339.05078},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1882}
}
Christina M. Mynhardt; Christopher M. van Bommel. Triangle Decompositions of Planar Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 643-659. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1882/
[1] B. Barber, D. Kühn, A. Lo and D. Osthus, Edge-decompositions of graphs with high minimum degree, arXiv:1410.5750v3, 2015. | Zbl 1346.05224
[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] N.L. Biggs, T.P. Kirkman, Mathematician, Bull. Lond. Math. Soc. 13 (1981) 97-120. doi:10.1112/blms/13.2.97[Crossref]
[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] | Zbl 1221.05070
[5] F. Dross, Fractional triangle decompositions in graphs with large minimum degree, arXiv:1503.08191v3, 2015.[WoS]
[6] O. Favaron, Z. Lonc and M. Truszczyński, Decompositions of graphs into graphs with three edges, Ars Combin. 20 (1985) 125-146. | Zbl 0604.05028
[7] K. Garaschuk, Linear Methods for Rational Triangle Decompositions, Doctoral Dissertation (University of Victoria, 2014). http://hdl.handle.net/1828/5665
[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] | Zbl 1053.05102
[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] | Zbl 1042.05083
[10] I. Holyer, The NP-completeness of some edge-partition problems, SIAM J. Comput. 10 (1981) 713-717. doi:10.1137/0210054[Crossref] | Zbl 0468.68069
[11] P. Keevash, The existence of designs, arXiv:1401.3665v1, 2014.
[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] T. Kirkman, On a problem in combinations, The Cambridge and Dublin Mathematical Journal (Macmillan, Barclay, and Macmillan) II (1847) 191-204.
[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] J. Steiner, Combinatorische Aufgaben, J. Reine Angew. Math. 45 (1853) 181-182. doi:10.1515/crll.1853.45.181[Crossref]
[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] D.B. West, Introduction to Graph Theory (Prentice Hall, Inc., Upper Saddle River, NJ, 1996). | Zbl 0845.05001
[18] W.S.B. Woolhouse, Prize question #1733, Lady’s and Gentleman’s Diary (1844) London, Company of Stationers.