Title of article :
The 3-choosability of plane graphs of girth 4
Author/Authors :
Peter C.B. Lam، نويسنده , , Wai Chee Shiu، نويسنده , , Zeng Min Song، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2005
Abstract :
A set image of vertices of the graph image is called image-reducible if the following is true: image is image-choosable if and only if image is image-choosable. A image-reduced subgraph image of image is a subgraph of image such that image contains no image-reducible set of some specific forms. In this paper, we show that a 3-reduced subgraph of a non-3-choosable plane graph image contains either adjacent 5-faces, or an adjacent 4-face and image-face, where image. Using this result, we obtain some sufficient conditions for a plane graph to be 3-choosable. In particular, if image is of girth 4 and contains no 5- and 6-cycles, then image is 3-choosable.
Keywords :
Choosability , Plane graph , Reduced subgraph
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics