On light subgraphs in plane graphs of minimum degree five

• Autorzy: Stanislav Jendrol' , Tomáš Madaras
• 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

EN

planar graph; light subgraph; star; triangulation

Kategorie tematyczne

• 05C10: Planar graphs; geometric and topological aspects of graph theory
• 05C75: Structural characterization of families of graphs
• 52B10: Three-dimensional polytopes

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1996
• Tom: 16
• Numer: 2
• Strony: 207-217

Daty

wydano

1996

otrzymano

1996-09-09

Twórcy

autor

Stanislav Jendrol'

• 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

autor

Tomáš Madaras

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

Identyfikatory

DOI

10.7151/dmgt.1035