Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs (Q1173768): Difference between revisions

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\).