On uniquely 3-colorable plane graphs without prescribed adjacent faces

Publication date 10 September 2015

Abstract: A graph

G

is emph{uniquely k-colorable} if the chromatic number of

G

is

k

and

G

has only one

k

-coloring up to permutation of the colors. For a plane graph

G

, two faces

f_{1}

and

f_{2}

of

G

are emph{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 3-colorable plane graph has adjacent

(3, k)

-faces, where

k l e q 5

. The bound 5 for

k

is best possible. Furthermore, we prove that there exist a class of uniquely 3-colorable plane graphs having neither adjacent

(3, i)

-faces nor adjacent

(3, j)

-faces, where

i, j i n 3, 4, 5

and

i e q j

. One of our constructions implies that there exist an infinite family of edge-critical uniquely 3-colorable plane graphs with

n

vertices and

f r a c 73 n - f r a c 143

edges, where

n (g e q 11)

is odd and

n e q u i v 2 p m o d 3

.

This page was built for publication: On uniquely 3-colorable plane graphs without prescribed adjacent faces