O. V. Borodin, A. O. Ivanova, “Planar graphs without triangular $4$-cycles are $3$-choosable”, Sib. Èlektron. Mat. Izv., 2008, Volume 5,Pages 75

This article is cited in 9 papers

Research papers

Planar graphs without triangular $4$-cycles are $3$-choosable

O. V. Borodin^a, A. O. Ivanova^b

^a Sobolev Institute of Mathematics, Novosibirsk, Russia
^b Yakutsk State University

Abstract: It is known that not all planar graphs are $4$-choosable (Margit Voigt, 1993), but those without $4$-cycles are $4$-choosable (Lam, Xu and Liu, 1999). We prove that all planar graphs without $4$-cycles adjacent to $3$-cycles are $4$-choosable.

UDC: 519.172.2

MSC: 05C15

Received February 27, 2008, published March 24, 2008

Language: English