Download PDF - On the structure of plane graphs of minimum face size 5All rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On the structure of plane graphs of minimum face size 5

Authors 1

Affiliations

  1. Institute of Mathematics, Faculty of Sciences, University of P.J. Šafárik, Jesenná 5, 041 54 Košice, Slovak Republic

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 known that a plane graph of minimum face size 5 contains light paths and a light pentagon. In this paper we show that every plane graph of minimum face size 5 contains also a light star K1,3 and we present a structural result concerning the existence of a pair of adjacent faces with degree-bounded vertices.

Keywords

ENG
plane graph, light graph, face size

Bibliography

  1. H. Enomoto and K. Ota, Connected Subgraphs with Small Degree Sums in 3-Connected Planar Graphs, J. Graph Theory 30 (1999) 191-203, doi: 10.1002/(SICI)1097-0118(199903)30:3<191::AID-JGT4>3.0.CO;2-X
  2. I. Fabrici, On vertex-degree restricted subgraphs in polyhedral graphs, Discrete Math. 256 (2002) 105-114, doi: 10.1016/S0012-365X(01)00368-5.
  3. I. Fabrici, J. Harant and S. Jendrol', Paths of low weight in planar graphs, submitted.
  4. I. Fabrici, E. Hexel, S. Jendrol' and H. Walther, On vertex-degree restricted paths in polyhedral graphs, Discrete Math. 212 (2000) 61-73, doi: 10.1016/S0012-365X(99)00209-5.
  5. I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs and Combin. 13 (1997) 245-250.
  6. I. Fabrici and S. Jendrol', Subgraphs with restricted degrees of their vertices in planar graphs, Discrete Math. 191 (1998) 83-90, doi: 10.1016/S0012-365X(98)00095-8.
  7. J. Harant, S. Jendrol' and M. Tkáč, On 3-connected plane graphs without triangular faces, J. Combin. Theory (B) 77 (1999) 150-161, doi: 10.1006/jctb.1999.1918.
  8. S. Jendrol', T. Madaras, R. Soták and Z. Tuza, On light cycles in plane triangulations, Discrete Math. 197/198 (1999) 453-467.
  9. S. Jendrol' and P. Owens, On light graphs in 3-connected plane graphs without triangular or quadrangular faces, Graphs and Combin. 17 (2001) 659-680, doi: 10.1007/s003730170007.
  10. A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Cas. SAV (Math. Slovaca) 5 (1955) 111-113.
  11. H. Lebesgue, Quelques consequences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 19-43.
  12. P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968.
Discussiones Mathematicae Graph Theory
2004/24/3
Export to PBN, Opens in new tab
Pages:
403-411
Main language of publication
English
Received
2003-01-28
Accepted
2004-04-16
Published
2004

DOI: 10.7151/dmgt.1239

Exact and natural sciences