On structure of some plane graphs with application to choosability

A graph G = (V, E) is (x. y)-choosable for integers x > y greater than or e qual to 1 if for any given family {A(v) \ v is an element of V} of sets A(v ) of cardinality x. there exists a collection {B(v) \ v is an element of V} of subsets B(v) subset of A(v) of cardinality y such that B(u) boolean AND B(v) = circle divide whenever uv, is an element of E(G). In this paper, st ructures of some plane graphs. including plane graphs with minimum degree 4 . are studied. Using these results, we may shove that if G is free of k-cyc les for some k is an element of {3, 4, 5, 6}, or if any two triangles in G have distance at least 2. then G is (4m, m)-choosable for all nonnegative i ntegers m. When m = 1, (4m, m)-choosable is simply 4-choosable. So these co nditions are also sufficient for a plane graph to be 4-choosable. (C) 2001 Academic Press.