On Uniquely 3-Colorable Plane Graphs without Adjacent Faces of Prescribed Degrees.

A graph G is uniquely k-colorable if the chromatic number of G is k and G has only one k-coloring up to the permutation of the colors. For a plane graph G, two faces f 1 and f 2 of G are adjacent (i , j) -faces if d (f 1) = i , d (f 2) = j , and f 1 and f 2 have a common edge, where d (f) is the degree of a face f. In this paper, we prove that every uniquely three-colorable plane graph has adjacent (3 , k) -faces, where k ≤ 5 . The bound of five for k is the best possible. Furthermore, we prove that there exists a class of uniquely three-colorable plane graphs having neither adjacent (3 , i) -faces nor adjacent (3 , j) -faces, where i , j are fixed in { 3 , 4 , 5 } and i ≠ j . One of our constructions implies that there exists an infinite family of edge-critical uniquely three-colorable plane graphs with n vertices and 7 3 n - 14 3 edges, where n (≥ 11) is odd and n ≡ 2 (mod 3) . [ABSTRACT FROM AUTHOR]