# On light subgraphs in plane graphs of minimum degree five

Stanislav Jendrol'; Tomáš Madaras

Discussiones Mathematicae Graph Theory (1996)

- Volume: 16, Issue: 2, page 207-217
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topStanislav Jendrol', and Tomáš Madaras. "On light subgraphs in plane graphs of minimum degree five." Discussiones Mathematicae Graph Theory 16.2 (1996): 207-217. <http://eudml.org/doc/270171>.

@article{StanislavJendrol1996,

abstract = {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.},

author = {Stanislav Jendrol', Tomáš Madaras},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {planar graph; light subgraph; star; triangulation; plane graph; subgraph; stars},

language = {eng},

number = {2},

pages = {207-217},

title = {On light subgraphs in plane graphs of minimum degree five},

url = {http://eudml.org/doc/270171},

volume = {16},

year = {1996},

}

TY - JOUR

AU - Stanislav Jendrol'

AU - Tomáš Madaras

TI - On light subgraphs in plane graphs of minimum degree five

JO - Discussiones Mathematicae Graph Theory

PY - 1996

VL - 16

IS - 2

SP - 207

EP - 217

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

LA - eng

KW - planar graph; light subgraph; star; triangulation; plane graph; subgraph; stars

UR - http://eudml.org/doc/270171

ER -

## References

top- [1] J.A. Bondy and U.S.R. Murty, Graph theory with applications (North Holland, Amsterdam 1976). Zbl1226.05083
- [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. Zbl0717.05034
- [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. Zbl0813.05020
- [4] I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs and Combinatorics (to appear). Zbl0891.05025
- [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). Zbl48.0664.02
- [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. Zbl35.0511.01

## Citations in EuDML Documents

top- Oleg V. Borodin, Douglas R. Woodall, Short cycles of low weight in normal plane maps with minimum degree 5
- Dávid Hudák, Tomás Madaras, On local structure of 1-planar graphs of minimum degree 5 and girth 4
- Oleg V. Borodin, Anna O. Ivanova, Tommy R. Jensen, 5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5
- Tomás Madaras, Note on the weight of paths in plane triangulations of minimum degree 4 and 5

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.