PDF
Discussiones Mathematicae Graph Theory 31(2) (2011)
333-344
DOI: https://doi.org/10.7151/dmgt.1549
ON DOUBLY LIGHT VERTICES IN PLANE GRAPHS
|
Veronika Kozáková and Tomás Madaras
Institute of Mathematics, Faculty of Sciences |
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
Close