Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces (Q1326890): Difference between revisions

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 (K1)--(K7) may indeed occur, independently of the other six, and moreover with the largest admissible parameter value. For example, there exists a polyhedron in which every edge is incident with a 10-vertex, i.e., it cannot contain any of configurations (K2)--(K7).