## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 285-296 |

Number of pages | 12 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 82 |

Issue number | 2 |

DOIs | |

Publication status | Published - Jul 2001 |

## Scopus Subject Areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## User-Defined Keywords

- Choosable; plane graph; cycle; triangle