Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs (Q1173768): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q505455 |
Changed an Item |
||
Property / author | |||
Property / author: Oleg V. Borodin / rank | |||
Normal rank |
Revision as of 17:45, 15 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs |
scientific article |
Statements
Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs (English)
0 references
25 June 1992
0 references
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\).
0 references
coloring
0 references
normal map
0 references
choosability
0 references