PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1996 | 16 | 2 | 207-217
Tytuł artykułu

On light subgraphs in plane graphs of minimum degree five

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars $K_{1,3}$ and $K_{1,4}$ and a light 4-path P₄. The results obtained for $K_{1,3}$ and P₄ are best possible.
Słowa kluczowe
Twórcy
  • Department of Geometry and Algebra, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic
  • Institute of Mathematics, Slovak Academy of Sciences, 041 54 Košice, Slovak Republic
  • Department of Geometry and Algebra, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic
Bibliografia
  • [1] J.A. Bondy and U.S.R. Murty, Graph theory with applications (North Holland, Amsterdam 1976).
  • [2] O.V. Borodin, Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs, Math. Notes 46 (1989) 835-837, doi: 10.1007/BF01139613.
  • [3] O.V. Borodin and D.P. Sanders, On light edges and triangles in planar graphs of minimum degree five, Math. Nachr. 170 (1994) 19-24, doi: 10.1002/mana.19941700103.
  • [4] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs and Combinatorics (to appear).
  • [5] P. Franklin, The four colour problem, Amer. J. Math. 44 (1922) 225-236; or in: N.L. Biggs, E.K. Lloyd, R.J. Wilson (eds.), Graph Theory 1737 - 1936 (Clarendon Press, Oxford 1977).
  • [6] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. źas. SAV (Math. Slovaca) 5 (1955) 111-113.
  • [7] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569-570.
  • [8] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1035
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ć.