Cyclic degrees of 3-polytopes
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.
scientific article; zbMATH DE number 1369700