RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2006 Volume 3, Pages 428–440 (Mi semr218)

This article is cited in 12 papers

Research papers

Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are $3$-colorable

O. V. Borodina, A. N. Glebova, T. R. Jensenb, A. Raspaudc

a Institute of Mathematics, Novosibirsk, Russia
b Alpen-Adria Universität Klagenfurt, Institut für Mathematik, Austria
c Université Bordeaux I, France

Abstract: Planar graphs without triangles adjacent to cycles of length from $3$ to $9$ are proved to be $3$-colorable, which extends Grötzsch's theorem. We conjecture that planar graphs without $3$-cycles adjacent to cycles of length $3$ or $5$ are $3$-colorable.

UDC: 519.172.2

MSC: 05C15

Received December 14, 2006, published December 23, 2006

Language: English



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024