Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9513624 | Discrete Mathematics | 2005 | 6 Pages |
Abstract
In 1995, Voigt constructed a planar triangle-free graph that is not 3-list-colorable. It has 166 vertices. Gutner then constructed such a graph with 164 vertices. We present two more graphs with these properties. The first graph has 97 vertices and a failing list assignment using triples from a set of six colors, while the second has 109 vertices and a failing list assignment using triples from a set of five colors.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
A.N. Glebov, A.V. Kostochka, V.A. Tashkinov,