On light subgraphs in plane graphs of minimum degree five

Stanislav Jendrol'; Tomáš Madaras

Discussiones Mathematicae Graph Theory, Tome 16 (1996), p. 207-217 / Harvested from The Polish Digital Mathematics Library

Access to full text
Full (PDF)

Résumé

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.

Publié le : 1996-01-01

Zbl 0877.05050

EUDML-ID : urn:eudml:doc:270171

@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1035,
     author = {Stanislav Jendrol' and Tom\'a\v s Madaras},
     title = {On light subgraphs in plane graphs of minimum degree five},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {16},
     year = {1996},
     pages = {207-217},
     zbl = {0877.05050},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1035}
}

Stanislav Jendrol'; Tomáš Madaras. On light subgraphs in plane graphs of minimum degree five. Discussiones Mathematicae Graph Theory, Tome 16 (1996) pp. 207-217. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1035/

Bibliographie

[000] [1] J.A. Bondy and U.S.R. Murty, Graph theory with applications (North Holland, Amsterdam 1976). | Zbl 1226.05083

[001] [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. | Zbl 0717.05034

[002] [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. | Zbl 0813.05020

[003] [4] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs and Combinatorics (to appear). | Zbl 0891.05025

[004] [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). | Zbl 48.0664.02

[005] [6] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. źas. SAV (Math. Slovaca) 5 (1955) 111-113.

[006] [7] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569-570.

[007] [8] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968. | Zbl 35.0511.01