TY - JOUR
T1 - On structure of some plane graphs with application to choosability
AU - Lam, Peter Che Bor
AU - Shiu, Wai Chee
AU - Xu, Baogang
N1 - Funding Information:
1Research is partially supported by Research Grant Council, Hong Kong; by Faculty Research Grant, Hong Kong Baptist University and by the Doctoral Foundation of the Education Commission of The People’s Republic of China.
PY - 2001/7
Y1 - 2001/7
N2 - A graph G=(V, E) is (x, y)-choosable for integers x>y≥1 if for any given family {A(v)|v∈V} of sets A(v) of cardinality x, there exists a collection {B(v)|v∈V} of subsets B(v)⊂A(v) of cardinality y such that B(u)∩B(v)=Ø whenever uv∈E(G). In this paper, structures of some plane graphs, including plane graphs with minimum degree 4, are studied. Using these results, we may show that if G is free of k-cycles for some k∈{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 integers m. When m=1, (4m, m)-choosable is simply 4-choosable. So these conditions are also sufficient for a plane graph to be 4-choosable.
AB - A graph G=(V, E) is (x, y)-choosable for integers x>y≥1 if for any given family {A(v)|v∈V} of sets A(v) of cardinality x, there exists a collection {B(v)|v∈V} of subsets B(v)⊂A(v) of cardinality y such that B(u)∩B(v)=Ø whenever uv∈E(G). In this paper, structures of some plane graphs, including plane graphs with minimum degree 4, are studied. Using these results, we may show that if G is free of k-cycles for some k∈{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 integers m. When m=1, (4m, m)-choosable is simply 4-choosable. So these conditions are also sufficient for a plane graph to be 4-choosable.
KW - Choosable; plane graph; cycle; triangle
UR - http://www.scopus.com/inward/record.url?scp=0035402202&partnerID=8YFLogxK
U2 - 10.1006/jctb.2001.2038
DO - 10.1006/jctb.2001.2038
M3 - Journal article
AN - SCOPUS:0035402202
SN - 0095-8956
VL - 82
SP - 285
EP - 296
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 2
ER -