zbMATH — the first resource for mathematics

Cyclic degrees of 3-polytopes. (English) Zbl 0930.05055
If \(G=(V,E,F)\) is a 3-polytope or a 3-connected plane graph, and \(v\in V\), then the cyclic degree \(d_{c}(v)\) is the number of other vertices that share incident faces with \(v\) and \(\Delta ^{*}(G)\) denotes the maximum face degree in \(G\). In this paper it is proved that if \(k\geq 3\) and \(G\) is a 3-polytope with \(\Delta ^{*}(G)\leq k\), then \(G\) has a vertex \(v\) with \(d(v)\leq 5\) and \(d_{c}(v)\leq M(k)\), where \(M(k)\) is given in the paper and is best possible for every \(k\geq 3\). Note that \(M(k)=k+3\) for \(17\leq k\leq 20\) and \(M(k)= k+2\) for every \(k\geq 21\). This implies improvements to some known upper bounds for the cyclic chromatic numbers of 3-polytopes.

05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
51M20 Polyhedra and polytopes; regular figures, division of spaces
Full Text: DOI