On doubly light vertices in plane graphs

Veronika Kozáková; Tomáš Madaras

ArticleOriginal scientific text

Title

On doubly light vertices in plane graphs

Authors ¹, ¹

Affiliations

Institute of Mathematics, Faculty of Sciences, University of P.J. Šafá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

ENG

plane graph, doubly light vertex

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).
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).
H. Lebesgue, Quelques consequences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 19-43.
P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413-426, doi: 10.1007/BF01444968.
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.

Title

On doubly light vertices in plane graphs

Affiliations

Abstract

Keywords

Bibliography