Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles. Issue 4 (30th March 2012)

• Record Type: Journal Article
• Authors: Borodin, Oleg V.; Ivanova, Anna O.
• Is Part Of: Journal of graph theory. Volume 72:Issue 4(2013)
• Page Start: 374
• Page End: 397
• Publication Date: 2012-03-30
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21647
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Every planar graph is known to be acyclically 7‐choosable and is conjectured to be acyclically 5‐choosable (O. V. Borodin, D. G. Fon‐Der‐Flaass, A. V. Kostochka, E. Sopena, J Graph Theory 40 (2002), 83–90). This conjecture if proved would imply both Borodin's (Discrete Math 25 (1979), 211–236) acyclic 5‐color theorem and Thomassen's (J Combin Theory Ser B 62 (1994), 180–181) 5‐choosability theorem. However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4‐ and 3‐choosable. In particular, the acyclic 4‐choosability was proved for the following planar graphs: without 3‐, 4‐, and 5‐cycles (M. Montassier, P. Ochem, and A. Raspaud, J Graph Theory 51 (2006), 281–300), without 4‐, 5‐, and 6‐cycles, or without 4‐, 5‐, and 7‐cycles, or without 4‐, 5‐, and intersecting 3‐cycles (M. Montassier, A. Raspaud, W. Wang, Topics Discrete Math (2006), 473–491), and neither 4‐ and 5‐cycles nor 8‐cycles having a triangular chord (M. Chen and A. Raspaud, Discrete Math. 310(15–16) (2010), 2113–2118). The purpose of this paper is to strengthen these results by proving that each planar graph without 4‐ and 5‐cycles is acyclically 4‐choosable.</p> </abstract>