Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces
type: Item
instance of: scholarly article
title: Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces
zbMATH Open document ID: 0795.05048
DOI: 10.1007/BF01208542
author: Oleg V. Borodin
published in: Mathematical Notes
publication date: 1994-07-13T00:00:00Z
review text: It is known that Euler polyhedra (which, by a theorem of E. Steinitz, are precisely the 3-connected planar graphs) contain a vertex of degree at most 5, a face of rank at most 5, and also either a vertex of degree 3 or a face of rank 3. There are also stronger results on the structure of polyhedra. Thus, any polyhedron contains one of the following elements: a 5-vertex incident with four triangles; a 4-vertex incident with a triangle; a 3-vertex incident with a triangle or a quadrilateral; or a pentagon incident with four 3-vertices; and the numbers figuring in this theorem cannot be improved. On the other hand, A. Kotzig proved the existence of a pair of adjacent vertices, the sum of whose degrees (weight) is at most 13; this bound is also best possible. In recent years Kotzig's theorem has been generalized and sharpened; some of the results have proved useful in studying the simultaneous coloring of different elements (vertices, edges, and faces) of planar graphs. These studies have actually been concerned with the minimal weight of weak, semiweak and strong edges in various classes of planar graphs. (An edge is weak if it is incident with two triangles, semiweak if it is incident with exactly one triangle and strong otherwise.) In this paper we will prove a preparatory result in that direction: Theorem 1. In any Euler polyhedron there exists at least one of the following configurations: (K1) a weak edge joining a 3-vertex to a vertex of degree at most 10; (K2) a weak edge joining a 4-vertex to a vertex of degree at most 7; (K3) a weak edge joining a 5-vertex incident with four triangles to a vertex of degree at most 6: (K4) a semiweak edge joining a 3-vertex to a vertex of degree at most 8; (K5) a semiweak edge joining a 4-vertex to a vertex of degree at most 5; (K6) an edge incident with a quadrilateral and joining a 3-vertex to a vertex of degree at most 5; (K7) a pentagon incident with four 3-vertices. In Section 2 we shall prove that each of the alternatives …
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 589612
zbMATH Keywords: Euler polyhedra
zbMATH Keywords: planar graphs
zbMATH Keywords: Kotzig's theorem
zbMATH Keywords: simultaneous coloring
zbMATH Keywords: faces
MaRDI profile type: Publication
cites work: Q4021376
cites work: Q3784093
cites work: On the total coloring of planar graphs.
cites work: Q3360218
cites work: Quelques consequences simples de la formule d'Euler
cites work: Q5344765
cites work: Q5528475
cites work: A seven-color theorem on the sphere
full work available at URL: https://doi.org/10.1007/bf01208542
OpenAlex ID: W2014586115
description: scientific article; zbMATH DE number 589612