
doi: 10.1007/bf01240258
In 1955 Kotzig proved that each 3-polytope contains an edge with the degree sum of its end vertices (weight) at most 13. Let \(e_{i,j}\) be the number of edges joining vertices of degree \(i\) with those of degree \(j\), and let \(\delta\) and \(\Delta\) be the minimum and maximum degrees of a graph under consideration. A plane map is normal if its faces have size at least three. Theorem 1. For any normal map with \(\delta\geq 3\), each of (a), (b) holds: (a) either there is an edge of weight at most 12 or \(e_{3,10}\geq 60\); (b) either there exists a cycle \([xyzu]\) with \(x\) and \(z\) having degree 3, or there exists an edge of weight at most 10, or else \(15e_{3,8}+5e_{4,7}+6e_{5,6}\geq 360\). A separating cycle is trivial if either its exterior or its interior contains vertices of degree 2 only. Theorem 2. In each normal map with \(\delta\geq 2\) there exists either a trivial 1- or 2-cycle, or an edge of weight at most 15, or else a cycle \([v_ 1v_ 2\cdots v_{2k}]\) with \(v_ 1,v_ 3,\dots,v_{2k-1}\) having degree 2. All parameters of Theorems 1 and 2 are the best possible. For the edge choosability number \(\tilde q\) introduced by \textit{V. G. Vizing} [Diskret. Analiz, Novosibirsk 29, 3-10 (1976; Zbl 0362.05060)] and \textit{P. Erdős, A. Rubin} and \textit{H. Taylor} [Combinatorics, graph theory and computing, Proc. West Coast Conf., Arcata/Calif. 1979, 125-157 (1980; Zbl 0469.05032)], these results imply Theorem 3. For any planar graph holds \(\tilde q\leq\Delta+1\) if \(\Delta\geq 9\), and \(q=\Delta\) if \(\Delta\geq 14\).
Coloring of graphs and hypergraphs, normal map, coloring, choosability, Planar graphs; geometric and topological aspects of graph theory
Coloring of graphs and hypergraphs, normal map, coloring, choosability, Planar graphs; geometric and topological aspects of graph theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
