Geodesic
An inequality concerning edges of minor weight in convex 3-polytopes
Discussiones Mathematicae. Graph Theory, Tome 16 (1996) no. 1, pp. 81-87.

Voir la notice de l'article provenant de la source Library of Science

Let e_ij be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is 20e_3,3 + 25e_3,4 + 16e_3,5 + 10e_3,6 + 6[2/3]e_3,7 + 5e_3,8 + 2[1/2]e_3,9 + 2e_3,10 + 16[2/3]e_4,4 + 11e_4,5 + 5e_4,6 + 1[2/3]e_4,7 + 5[1/3]e_5,5 + 2e_5,6 ≥ 120; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.
Keywords: planar graph, convex 3-polytope, normal map 
@article{DMGT_1996_16_1_a5,
     author = {Fabrici, Igor and Jendrol', Stanislav},
     title = {An inequality concerning edges of minor weight in convex 3-polytopes},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {81--87},
     publisher = {mathdoc},
     volume = {16},
     number = {1},
     year = {1996},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1996_16_1_a5/}
}
TY  - JOUR
AU  - Fabrici, Igor
AU  - Jendrol', Stanislav
TI  - An inequality concerning edges of minor weight in convex 3-polytopes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1996
SP  - 81
EP  - 87
VL  - 16
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1996_16_1_a5/
LA  - en
ID  - DMGT_1996_16_1_a5
ER  - 
%0 Journal Article
%A Fabrici, Igor
%A Jendrol', Stanislav
%T An inequality concerning edges of minor weight in convex 3-polytopes
%J Discussiones Mathematicae. Graph Theory
%D 1996
%P 81-87
%V 16
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1996_16_1_a5/
%G en
%F DMGT_1996_16_1_a5
Fabrici, Igor; Jendrol', Stanislav. An inequality concerning edges of minor weight in convex 3-polytopes. Discussiones Mathematicae. Graph Theory, Tome 16 (1996) no. 1, pp. 81-87. http://geodesic.mathdoc.fr/item/DMGT_1996_16_1_a5/

[1] O. V. Borodin, Computing light edges in planar graphs, in: R. Bodendiek, R. Henn, eds., Topics in Combinatorics and Graph Theory (Physica-Verlag, Heidelberg, 1990) 137-144.

[2] O. V. Borodin, Structural properties and colorings of plane graphs, Ann. Discrete Math. 51 (1992) 31-37, doi: 10.1016/S0167-5060(08)70602-2.

[3] O. V. Borodin, Precise lower bound for the number of edges of minor weight in planar maps, Math. Slovaca 42 (1992) 129-142.

[4] O. V. Borodin, Structural properties of planar maps with the minimal degree 5, Math. Nachr. 158 (1992) 109-117, doi: 10.1002/mana.19921580108.

[5] O. V. Borodin and D. P. Sanders, On light edges and triangles in planar graph of minimum degree five, Math. Nachr. 170 (1994) 19-24, doi: 10.1002/mana.19941700103.

[6] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390-408, doi: 10.1007/BF02764716.

[7] B. Grünbaum, Polytopal graphs, in: D. R. Fulkerson, ed., Studies in Graph Theory, MAA Studies in Mathematics 12 (1975) 201-224.

[8] B. Grünbaum, New views on some old questions of combinatorial geometry, Int. Teorie Combinatorie, Rome, 1973, 1 (1976) 451-468.

[9] B. Grünbaum and G. C. Shephard, Analogues for tiling of Kotzig's theorem on minimal weights of edges, Ann. Discrete Math. 12 (1982) 129-140.

[10] J. Ivančo, The weight of a graph, Ann. Discrete Math. 51 (1992) 113-116, doi: 10.1016/S0167-5060(08)70614-9.

[11] J. Ivančo and S. Jendrol', On extremal problems concerning weights of edges of graphs, in: Coll. Math. Soc. J. Bolyai, 60. Sets, Graphs and Numbers, Budapest (Hungary) 1991 (North Holland, 1993) 399-410.

[12] E. Jucovič, Strengthening of a theorem about 3-polytopes, Geom. Dedicata 3 (1974) 233-237, doi: 10.1007/BF00183214.

[13] E. Jucovič, Convex 3-polytopes (Veda, Bratislava, 1981, Slovak).

[14] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. as. SAV (Math. Slovaca) 5 (1955) 101-103 (Slovak; Russian summary).

[15] A. Kotzig, From the theory of Euler's polyhedra, Mat. as. (Math. Slovaca) 13 (1963) 20-34 (Russian).

[16] O. Ore, The four-color problem (Academic Press, New York, 1967).

[17] J. Zaks, Extending Kotzig's theorem, Israel J. Math. 45 (1983) 281-296, doi: 10.1007/BF02804013.