PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 3 | 643-659
Tytuł artykułu

Triangle Decompositions of Planar Graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
3
Strony
643-659
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2015-04-15
poprawiono
2015-10-06
zaakceptowano
2015-10-06
online
2016-07-06
Twórcy
  • Department of Mathematics and Statistics University of Victoria P.O. Box 1700 STN CSC Victoria, BC, Canada V8W 2Y2, kieka@uvic.ca
  • 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, cvanbomm@uwaterloo.ca
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1882
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.