✍ Scribed by Daniel P. Sanders; Yue Zhao
No coin nor oath required. For personal study only.
This paper proves the conjecture of Horn ˘a ´k and Jendrol' that the faces of a convex polyhedron with maximum vertex degree D can be colored with 1+(D+7)(D -1) d colors in such a way that each pair of faces that are distance at most d apart receives different colors. © 2002 Elsevier Science (USA) between 3-connected plane graphs and the 1-skeletons of convex polyhedra. The theorems presented in this paper will apply to 3-connected plane graphs.
A k-face coloring of a plane graph G is an assignment to each face of the graph a color in {1, ..., k}. A face coloring is proper if each pair of distinct faces which have a common edge in their boundaries receive different colors. The Four Color Theorem states that every plane graph has a proper 4-coloring. This was first proved by Appel and Haken (see ). For an improved proof, see .
A face coloring is angular if each pair of distinct faces whose boundaries intersect receive different colors. Clearly, there is no finite bound on the number of colors required in an angular coloring of a plane graph. For a pie chart with n slices, an angular coloring must use n colors.
In general, for a vertex or face x of G, let the degree of x be the number of edges incident with x. Given a graph G, let D(G), or simply D if the graph is clear from the context, be the maximum degree of a vertex of G. For any graph, D is a lower bound for the number of colors required in an angular coloring. In , a class of plane graphs is given which require N 3 2 DM colors in any angular coloring. In (see also Problem 2.5 of [13]), Borodin conjectured that every plane graph may be colored with this many colors. This conjecture has been proved only for D=3 (equivalent to the Four Color Theorem) and for D=4 [4] (see also ). Ore and Plummer [14] gave an upper bound of 2D, which was improved to N 9 5 DM by the authors with Borodin . The best known upper bound is K 5 3 DL, given by the authors .
Much tighter results are known for 3-connected plane graphs. Plummer and Toft proved that every 3-connected plane graph has an angular (D+9)-coloring. They gave a class of graphs which give a lower bound of D+2, which they conjectured to be best possible. Borodin (see Problem 2.5 of ) has improved this, showing that every 3-connected plane graph with D \ 24 has an angular (D+3)-coloring. In 1999, Horn ˘a ´k and Jendrol' proved that every 3-connected plane graph with D \ 24 has an angular (D+2)-coloring. Recently, it is proved by Enomoto et al.
[8] that any 3-connected plane graph with D \ 60 has an angular (D+1)-coloring (which is the best possible general bound because of D-gonal pyramid).
Horn ˘a ´k and Jendrol' defined d-distance colorings as a generalization both of angular colorings and diagonal colorings (see, e.g., or Problems 2.15 and 3.10 of ). Two vertices of a connected graph are distance d apart if the shortest path connecting them has d edges. A face coloring is d-distance if each pair of faces which are incident with vertices that are distance at most d apart receive different colors. Thus the distance between two faces which receive the same color must be greater than d. An angular coloring is a 0-distance coloring, and a diagonal coloring is a 1-distance coloring. In , Horn ˘a ´k and Jendrol' showed that connected FACES OF CONVEX POLYHEDRA
📜 SIMILAR VOLUMES