Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs (Q1173768): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The NP-Completeness of Edge-Coloring / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: List-colourings of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Colour Numbers of Complete Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A seven-color theorem on the sphere / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3679212 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3784093 / rank | |||
Normal rank |
Latest revision as of 09:44, 15 May 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