On the Weight of Minor Faces in Triangle-Free 3-Polytopes

Oleg V. Borodin; Anna O. Ivanova

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 603-619
  • ISSN: 2083-5892

Abstract

top
The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp. The purpose of this paper is to improve this 21 to 20, which is best possible.

How to cite

top

Oleg V. Borodin, and Anna O. Ivanova. "On the Weight of Minor Faces in Triangle-Free 3-Polytopes." Discussiones Mathematicae Graph Theory 36.3 (2016): 603-619. <http://eudml.org/doc/285603>.

@article{OlegV2016,
abstract = {The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp. The purpose of this paper is to improve this 21 to 20, which is best possible.},
author = {Oleg V. Borodin, Anna O. Ivanova},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {plane map; plane graph; 3-polytope; structural property; weight of face},
language = {eng},
number = {3},
pages = {603-619},
title = {On the Weight of Minor Faces in Triangle-Free 3-Polytopes},
url = {http://eudml.org/doc/285603},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Oleg V. Borodin
AU - Anna O. Ivanova
TI - On the Weight of Minor Faces in Triangle-Free 3-Polytopes
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 603
EP - 619
AB - The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp. The purpose of this paper is to improve this 21 to 20, which is best possible.
LA - eng
KW - plane map; plane graph; 3-polytope; structural property; weight of face
UR - http://eudml.org/doc/285603
ER -

References

top
  1. [1] S.V. Avgustinovich and O.V. Borodin, Neighborhoods of edges in normal maps, Diskretn. Anal. Issled. Oper. 2 (1995) 3-9, in Russian. Zbl0856.05031
  2. [2] O.V. Borodin, Solution of Kotzig’s and Grünbaum’s problems on the separability of a cycle in a planar graph, Mat. Zametki 46 (1989) 9-12, in Russian. 
  3. [3] O.V. Borodin, Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps, Diskret. Mat. 3 (1991) 24-27, in Russian. Zbl0742.05034
  4. [4] O.V. Borodin, Minimal weight of a face in plane triangulations without 4-vertices, Mat. Zametki 51 (1992) 16-19, in Russian. Zbl0755.05091
  5. [5] O.V. Borodin, Triangulated 3-polytopes with restricted minimal weight of faces, Discrete Math. 186 (1998) 281-285. doi:10.1016/S0012-365X(97)00240-9[Crossref] 
  6. [6] O.V. Borodin and D.V. Loparev, The height of small faces in planar normal maps, Diskretn. Anal. Issled. Oper. 5 (1998) 6-17, in Russian. Zbl0913.05039
  7. [7] O.V. Borodin and D.R. Woodall, The weight of faces in plane maps, Mat. Zametki 64 (1998) 648-657, in Russian. Zbl0958.52015
  8. [8] O.V. Borodin and D.R. Woodall, Cyclic degrees of 3-polytopes, Graphs Combin. 15 (1999) 267-277.[Crossref] Zbl0930.05055
  9. [9] O.V. Borodin, An improvement of Lebesgue’s theorem on the structure of minor faces of 3-polytopes, Diskretn. Anal. Issled. Oper. 9 (2002) 29-39, in Russian. Zbl1015.52008
  10. [10] O.V. Borodin, Colorings of plane graphs: a survey, Discrete Math. 313 (2013) 517-539. doi:10.1016/j.disc.2012.11.011[Crossref] Zbl1259.05042
  11. [11] O.V. Borodin and A.O. Ivanova, Describing 3-faces in normal plane maps with minimum degree 4, Discrete Math. 313 (2013) 2841-2847. doi:10.1016/j.disc.2013.08.028[Crossref][WoS] 
  12. [12] O.V. Borodin, A.O. Ivanova and A.V. Kostochka, Describing faces in plane triangulations, Discrete Math. 319 (2014) 47-61. doi:10.1016/j.disc.2013.11.021[WoS][Crossref] Zbl1280.05027
  13. [13] O.V. Borodin, A.O. Ivanova and D.R. Woodall, Light C4 and C5 in 3-polytopes with minimum degree 5, Discrete Math. 334 (2014) 63-69. doi:10.1016/j.disc.2014.06.024[Crossref] Zbl1298.05083
  14. [14] O.V. Borodin, A.O. Ivanova and A.V. Kostochka, Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11, Discrete Math. 315-316 (2014) 128-134. doi:10.1016/j.disc.2013.10.021[Crossref] Zbl1278.05080
  15. [15] O.V. Borodin and A.O. Ivanova, The vertex-face weight of edges in 3-polytopes, Sibirsk. Mat. Zh. 56 (2015) 338-350, in Russian.[WoS] Zbl1331.52018
  16. [16] O.V. Borodin and A.O. Ivanova, Every 3-polytope with minimum degree 5 has a 7-cycle with maximum degree at most 15, Sibirsk. Mat. Zh. 56 (2015) 775-789, in Russian. Zbl06501740
  17. [17] B. Ferencová and T. Madaras, On the structure of polyhedral graphs with prescribed edge and dual edge weight , Acta Univ. M. Belii Ser. Math. 12 (2005) 13-18.  Zbl1103.05026
  18. [18] B. Ferencová and T. Madaras, Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight , Discrete Math. 310 (2010) 1661-1675. doi:10.1016/j.disc.2009.11.027[WoS][Crossref] Zbl1222.05217
  19. [19] B. Grünbaum, Polytopal graphs, in: Studies in Graph Theory, D.R. Fulkerson, Ed., MAA Studies in Mathematics 12 (1975) 201-224. 
  20. [20] M. Horňák and S. Jendroľ, Unavoidable sets of face types for planar maps, Discuss. Math. Graph Theory 16 (1996) 123-142. doi:10.7151/dmgt.1028[Crossref] Zbl0877.05048
  21. [21] S. Jendroľ, Triangles with restricted degrees of their boundary vertices in plane triangulations, Discrete Math. 196 (1999) 177-196. doi:10.1016/S0012-365X(98)00172-1[Crossref] 
  22. [22] S. Jendroľ and H.-J. Voss, Light subgraphs of graphs embedded in the plane and in the projective plane-a survey, Discrete Math. 313 (2013) 406-421. doi:10.1016/j.disc.2012.11.007[Crossref][WoS] Zbl1259.05045
  23. [23] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. Čas. 5 (1955) 101-113, in Russian. 
  24. [24] A. Kotzig, From the theory of Eulerian polyhedra, Mat. Čas. 13 (1963) 20-34. Zbl0134.19601
  25. [25] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569-570. 
  26. [26] H. Lebesgue, Quelques conséquences simples de la formule d’Euler , J. Math. Pures Appl. 19 (1940) 27-43. Zbl0024.28701
  27. [27] T. Madaras and R. Škrekovski, Heavy paths, light stars, and big melons, Discrete Math. 286 (2004) 115-131. doi:10.1016/j.disc.2013.11.052[Crossref] Zbl1053.05035
  28. [28] T. Madaras and R. Soták, The 10-cycle C10 is light in the family of all plane triangulations with minimum degree five, Tatra Mt. Math. Publ. 18 (1999) 35-56. Zbl0951.05031
  29. [29] T. Madaras, R. Škrekovski and H.-J. Voss, The 7-cycle C7 is light in the family of planar graphs with minimum degree 5, Discrete Math. 307 (2007) 1430-1435. doi:10.1016/j.disc.2005.11.080[Crossref] Zbl1115.05022
  30. [30] B.Mohar, R. Škrekovski and H.-J. Voss, Light subraphs in planar graphs of minimum degree 4 and edge-degree 9, J. Graph Theory 44 (2003) 261-295. doi:10.1002/jgt.10144[Crossref] Zbl1031.05075
  31. [31] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, Recent Progress in Combinatorics, W.T. Tutte, Ed. (Academic Press, New York, 1969) 287-293. Zbl0195.25701
  32. [32] M.D. Plummer, On the cyclic connectivity of planar graph, Graph Theory and Application (Springer-Verlag, Berlin, 1972) 235-242. 
  33. [33] M.D. Plummer and B. Toft, Cyclic coloration of 3-polytopes, J. Graph Theory 11 (1987) 507-515. doi:10.1002/jgt.3190110407 [Crossref] 
  34. [34] E. Steinitz, Polyheder und Raumeinteilungen, Enzykl. Math. Wiss. (Geometrie) 3AB (1922) 1-139. 
  35. [35] P. Wernicke, Über den Kartographischen Vierfarbensatz , Math. Ann. 58 (1904) 413-426. Zbl35.0511.01

NotesEmbed ?

top

You must be logged in to post comments.