Research papers

On planar graphs without list $3$-coloring

V. A. Tashkinov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: We construct a planar graph without $4$-and $5$-cycles and without intersecting triangles that has $366$ vertices and no list $3$-coloring from a set of $4$ colors.

Keywords: planar graph, list coloring, $3$-choosability.

UDC: 519.17

MSC: 05C

Received August 14, 2008, published December 16, 2008

Bibliographic databases:

•