A set S of vertices of the graph G is called k-reducible if the following is true: G is k-choosable if and only if G-S is k-choosable. A k-reduced subgraph H of G is a subgraph of G such that H contains no k-reducible set of some specific forms. In this paper, we show that a 3-reduced subgraph of a non-3-choosable plane graph G contains either adjacent 5-faces, or an adjacent 4-face and k-face, where k≤6. Using this result, we obtain some sufficient conditions for a plane graph to be 3-choosable. In particular, if G is of girth 4 and contains no 5- and 6-cycles, then G is 3-choosable.
Scopus Subject Areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Plane graph
- Reduced subgraph