Article ID Journal Published Year Pages File Type
9513624 Discrete Mathematics 2005 6 Pages PDF
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
, , ,