Geodesic
Triangle Decompositions of Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 643-659.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: planar graphs, triangle decompositions, rational triangle decompositions 
@article{DMGT_2016_36_3_a9,
     author = {Mynhardt, Christina M. and Bommel, Christopher M. van},
     title = {Triangle {Decompositions} of {Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {643--659},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a9/}
}
TY  - JOUR
AU  - Mynhardt, Christina M.
AU  - Bommel, Christopher M. van
TI  - Triangle Decompositions of Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 643
EP  - 659
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a9/
LA  - en
ID  - DMGT_2016_36_3_a9
ER  - 
%0 Journal Article
%A Mynhardt, Christina M.
%A Bommel, Christopher M. van
%T Triangle Decompositions of Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 643-659
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a9/
%G en
%F DMGT_2016_36_3_a9
Mynhardt, Christina M.; Bommel, Christopher M. van. Triangle Decompositions of Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 643-659. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a9/

[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

[3] N.L. Biggs, T.P. Kirkman, Mathematician, Bull. Lond. Math. Soc. 13 (1981) 97-120. doi:10.1112/blms/13.2.97

[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

[5] F. Dross, Fractional triangle decompositions in graphs with large minimum degree, arXiv:1503.08191v3, 2015.

[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

[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

[10] I. Holyer, The NP-completeness of some edge-partition problems, SIAM J. Comput. 10 (1981) 713-717. doi:10.1137/0210054

[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

[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

[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

[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.