DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 31(2) (2011) 333-344
DOI: 10.7151/dmgt.1549

ON DOUBLY LIGHT VERTICES IN PLANE GRAPHS

Veronika Kozáková  and  Tomás Madaras

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

Abstract

A vertex is said to be doubly light in a family of plane graphs if its degree and sizes of neighbouring faces are bounded above by a finite constant. We provide several results on the existence of doubly light vertices in various families of plane graph.

Keywords: plane graph, doubly light vertex.

2010 Mathematics Subject Classification: 05C10.

References

[1] O.V. Borodin, Solution of Kotzig-Grünbaum problems on separation of a cycle in planar graphs, Mat. Zametki 46 (1989) 9-12 (in Russian).
[2] O.V. Borodin, Sharpening Lebesgue's theorem on the structure of lowest faces of convex polytopes, Diskretn. Anal. Issled. Oper., Ser. 1 9, No. 3 (2002) 29-39 (in Russian).
[3] H. Lebesgue, Quelques consequences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 19-43.
[4] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968.
[5] R. Radoicic and G. Tóth, The discharging method in combinatorial geometry and the Pach-Sharir conjecture, Contemp. Math. 453 (2008) 319-342, doi: 10.1090/conm/453/08806.

Received 16 November 2009
Revised 3 June 2010
Accepted 9 June 2010