Triangle Decompositions of Planar Graphs

• Autorzy: Christina M. Mynhardt , Christopher M. van Bommel
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

planar graphs; triangle decompositions; rational triangle decompositions

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 643-659

Daty

wydano

2016-08-01

otrzymano

2015-04-15

poprawiono

2015-10-06

zaakceptowano

2015-10-06

online

2016-07-06

Twórcy

autor

Christina M. Mynhardt

• Department of Mathematics and Statistics University of Victoria P.O. Box 1700 STN CSC Victoria, BC, Canada V8W 2Y2

autor

Christopher M. van Bommel

• Department of Mathematics and Statistics University of Victoria P.O. Box 1700 STN CSC Victoria, BC, Canada V8W 2Y2, PhD student, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada

Bibliografia

• [1] B. Barber, D. Kühn, A. Lo and D. Osthus, Edge-decompositions of graphs with high minimum degree, arXiv:1410.5750v3, 2015.
• [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]
• [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.
• [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]
• [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]
• [10] I. Holyer, The NP-completeness of some edge-partition problems, SIAM J. Comput. 10 (1981) 713-717. doi:10.1137/0210054[Crossref]
• [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).
• [18] W.S.B. Woolhouse, Prize question #1733, Lady’s and Gentleman’s Diary (1844) London, Company of Stationers.

Identyfikatory

DOI

10.7151/dmgt.1882