PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 1 | 227-238
Tytuł artykułu

Light Graphs In Planar Graphs Of Large Girth

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w for light K1,3 and C10.
Słowa kluczowe
Wydawca
Rocznik
Tom
36
Numer
1
Strony
227-238
Opis fizyczny
Daty
wydano
2016-02-01
otrzymano
2015-02-06
poprawiono
2015-06-08
zaakceptowano
2015-06-08
online
2016-01-19
Twórcy
autor
  • Institute of Mathematics, P.J.Šafárik University in Košice Jesenná 5, 04001 Košice, Slovakia, tomas.madaras@upjs.sk
  • Institute of Mathematics, P.J.Šafárik University in Košice Jesenná 5, 04001 Košice, Slovakia, siroczki@gmail.com
Bibliografia
  • [1] K. Appel and W. Haken, Every Planar Map is Four-Colorable (Providence, RI, American Mathematical Society, 1989). doi:10.1090/conm/098[Crossref]
  • [2] O.V. Borodin, Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs, Mat. Zametki 46(5) (1989) 9–12.
  • [3] D.W. Cranston and D.B. West, A guide to the discharging method, arXiv:1306.4434 [math.CO] (2013).
  • [4] S. Jendrol’ and M. Maceková, Describing short paths in plane graphs of girth at least 5, Discrete Math. 338 (2015) 149–158. doi:10.1016/j.disc.2014.09.014[Crossref][WoS]
  • [5] S. Jendrol’, M. Maceková and R. Soták, Note on 3-paths in plane graphs of girth 4, Discrete Math. 338 (2015) 1643–1648. doi:/10.1016/j.disc.2015.04.011
  • [6] S. Jendrol’, M. Maceková, M. Montassier and R. Soták, Unavoidable 3-paths in planar graphs of given girth, manuscript.
  • [7] S. Jendrol’ and P.J. Owens, On light graphs in 3-connected plane graphs without triangular or quadrangular faces, Graphs Combin. 17 (2001) 659–680. doi:10.1007/s003730170007[Crossref]
  • [8] S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in the plane - A survey, Discrete Math. 313 (2013) 406–421. doi:10.1016/j.disc.2012.11.007[Crossref][WoS]
  • [9] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.Čas. SAV (Math. Slovaca) 5 (1955) 101–113.
  • [10] H. Lebesgue, Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. 19 (1940) 27–43.
  • [11] N. Robertson, D.P. Sanders, P.D. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997) 2–44. doi:10.1006/jctb.1997.1750[Crossref]
  • [12] D.B. West, Introduction to Graph Theory (Prentice Hall, 2001).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1847
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ć.