Ordinary 3-polytopes

We introduce a class of three-dimensional polytopesP with the property that there is a total ordering of the vertices ofP that determines completely the facial structure ofP. This class contains the cyclic 3-polytopes.     

On smallest 3-polytopes of given graph radius

The 3-polytopes are planar, 3-connected graphs. A classical question is, given $r\ge 3$, is the $2(r?1)$-gonal prism $K_2\times C_{2(r?1)}$ the unique 3-polytope of graph radius r and smallest size? Under some extra assumptions, we answer this question in the positive.     

On face-vectors of 5-valent convex 3-polytopes

For a convex 3-polytope P let p_k (P) denote the number of its k-gonal faces. A sequence (p_k(P)¦k3) associated with P in a natural way is said to be the face-vector of P. A sequence p = (p_k¦k3) of non-negative integers is said to be 5-realizable provided that there exists a 5-valent 3-polytope P such that p_k (P) = p_k for all k3. In the present paper a new necessary condition as well as a few new sufficient conditions are obtained for 5-realizability of sequences p.Dedicated to Professor N.K. Stephanidis on his 65th birthday     

On Hamilton decompositions of prisms over simple 3-polytopes

In this paper it is shown that certain families of simple 4-polytopes have a Hamilton decomposition, that is, the edges of these polytopes can be partitioned into two Hamilton cycles.This research was partially supported by N.S.E.R.C. under Grant A-4792.     

Projections of 3-polytopes

Given any 3-dimensional convex polytopeP, and any simple circuitC in the 1-skeleton ofP, there is a convex polytopeP′ combinatorially equivalent toP, and a direction such that ifP′ is projected orthogonally in this direction, then the inverse image of the boundary of the projection is the circuit inP′ corresponding to the circuitC inP. Research supported by NSF Grant GP-8470.     

On the development of closed convex curves on 3-polytopes

It is shown that a closed convex polygonal curve on the surface of a 3-polytope develops in the plane to a simple path: it does not self-intersect.     

On periodically-cyclic Gale 4-polytopes

Based upon a labelling (total ordering) of vertices, a 4-polytope is Gale if the vertices satisfy a part of Gale's Evenness Condition and it is periodically-cyclic if there is an integer k such that every subset of k successive vertices generates a cyclic 4-polytope. Among the bi-cyclic 4-polytopes introduced by Smilansky, we determine which are Gale or periodically-cyclic or both.     

An inequality for 3-polytopes

We prove the inequality Σ_n≥7 (n−6) p_n≤v−12 for any 3-dimensional polytope with v vertices and p_n n-sided faces, such that Σ_n≥6 p_n≥3. The polytopes satisfying Σ_n≥7 (n−6) p_n=v−12 are described and an interpretation of our results is given in terms of density of n-sided faces in planar graphs.     

Cyclic coloration of 3-polytopes

A cyclic coloration of a planar graph G is an assignment of colors to the points of G such that for any face bounding cycle the points of F have different colors. We observe that the upper bound 2ρ*(G), due to O. Ore and M. D. Plummer, can be improved to ρ*(G) + 9 when G is 3-connected (ρ* denotes the size of a maximum face). The proof uses two principal tools: the theory of Euler contributions and recent results on contractible lines in 3-connected graphs by K. Ando, H. Enomoto and A. Saito.     

Links and cubic 3-polytopes

It is well known that a prime link diagram corresponds to a signed plane graph without cut vertices (Kauffman, 1989). In this paper, we present a new relation between prime links and cubic 3-polytopes. Let be the set of links such that each has a diagram whose corresponding signed plane graph is the graph of a cubic 3-polytope. We show that all nontrivial prime links, except -torus links and -pretzel links, can be obtained from by using some operation of untwining. Furthermore, we define the generalized cubic 3-polytope chains and then show that any nontrivial link can be obtained from by some untwining operations, where is the set of links corresponding to generalized cubic 3-polytope chains. These results are used to simplify the computation of the Kauffman brackets of links so that the computing can be done in a unified way for many infinite families of links.

     

Low minor faces in 3-polytopes

It is trivial that every 3-polytope has a face of degree at most 5, called minor. The height $h\left(f\right)$ of a face $f$ is the maximum degree of the vertices incident with $f$. It follows from the partial double $n$-pyramids that $h\left(f\right)$ can be arbitrarily large for each $f$ if a 3-polytope is allowed to have faces of types $(4,4,\infty )$ or $(3,3,3,\infty )$.In 1996, M. Horňák and S. Jendrol’ proved that every 3-polytope without faces of types $(4,4,\infty )$ and$(3,3,3,\infty )$ has a minor face of height at most 39 and constructed such a 3-polytope satisfying $h\left(f\right)\ge 30$ for all minor faces $f$.The purpose of this paper is to prove that every 3-polytope without faces of types $(4,4,\infty )$ and$(3,3,3,\infty )$ has a minor face of height at most 30, which bound is tight due to the Horňák–Jendrol’ construction.     

The height of faces of 3-polytopes

The height of a face in a 3-polytope is the maximum degree of the incident vertices of the face, and the height of a 3-polytope, h, is the minimum height of its faces. A face is pyramidal if it is either a 4-face incident with three 3-vertices, or a 3-face incident with two vertices of degree at most 4. If pyramidal faces are allowed, then h can be arbitrarily large; so we assume the absence of pyramidal faces. In 1940, Lebesgue proved that every quadrangulated 3-polytope has h ≤ 11. In 1995, this bound was lowered by Avgustinovich and Borodin to 10. Recently, we improved it to the sharp bound 8. For plane triangulation without 4-vertices, Borodin (1992), confirming the Kotzig conjecture of 1979, proved that h ≤ 20 which bound is sharp. Later, Borodin (1998) proved that h ≤ 20 for all triangulated 3-polytopes. Recently, we obtained the sharp bound 10 for triangle-free 3-polytopes. In 1996, Horňák and Jendrol’ proved for arbitrarily 3-polytopes that h ≤ 23. In this paper we improve this bound to the sharp bound 20.     

Cyclic degree and cyclic coloring of 3-polytopes

A vertex coloring of a plane graph is called cyclic if the vertices in each face bounding cycle are colored differently. The main result is an improvement of the upper bound for the cyclic chromatic number of 3-polytopes due to Plummer and Toft, 1987 (J. Graph Theory 11 (1987) 505–517). The proof is based on a structural property of 3-polytopes, in a sense stronger than that implied by Lebesgue's theorem of 1940. Namely, precise upper bound is obtained for the minimum cyclic degree of 3-polytopes with the maximum face size at least 24. © 1996 John Wiley & Sons, Inc.     

Equifacetted 4-polytopes

Many polyhedra (convex 3-polytopes) are known which occur as facets (3-faces) of convex 4-polytopes. The purpose of this paper is to determine the combinatorial types of infinitely many more polyhedra with this property. This is achieved by determining the facets of polar bicyclic polytopes.     

Describing 4-paths in 3-polytopes with minimum degree 5

Back in 1922, Franklin proved that each 3-polytope with minimum degree 5 has a 5-vertex adjacent to two vertices of degree at most 6, which is tight. This result has been extended and refined in several directions. In particular, Jendrol’ and Madaras (1996) ensured a 4-path with the degree-sum at most 23. The purpose of this note is to prove that each 3-polytope with minimum degree 5 has a (6, 5, 6, 6)-path or (5, 5, 5, 7)-path, which is tight and refines both above mentioned results.     

Joint extension of two theorems of Kotzig on 3-polytopes

The weight of an edge in a graph is the sum of the degrees of its end-vertices. It is proved that in each 3-polytope there exists either an edge of weight at most 13 for which both incident faces are triangles, or an edge of weight at most 10 which is incident with a triangle, or else an edge of weight at most 8. All the bounds 13, 10, and 8 are sharp and attained independently of each other.