Smaller planar triangle-free graphs that are not 3-list-colorable

A. N. Glebov; A. V. Kostochka; V. A. Tashkinov

doi:10.1016/j.disc.2004.10.015

Smaller planar triangle-free graphs that are not 3-list-colorable

A. N. Glebov, A. V. Kostochka, V. A. Tashkinov

Mathematics

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	269-274
Number of pages	6
Journal	Discrete Mathematics
Volume	290
Issue number	2-3
DOIs	https://doi.org/10.1016/j.disc.2004.10.015
State	Published - Feb 28 2005

Keywords

List coloring
Planar graphs
Triangle-free graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2004.10.015

Library availability

Discover UIUC Full Text

Cite this

@article{4ba60d59e83c4afaa04c5224977186a5,

title = "Smaller planar triangle-free graphs that are not 3-list-colorable",

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.",

keywords = "List coloring, Planar graphs, Triangle-free graphs",

author = "Glebov, {A. N.} and Kostochka, {A. V.} and Tashkinov, {V. A.}",

year = "2005",

month = feb,

day = "28",

doi = "10.1016/j.disc.2004.10.015",

language = "English (US)",

volume = "290",

pages = "269--274",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2-3",

}

TY - JOUR

T1 - Smaller planar triangle-free graphs that are not 3-list-colorable

AU - Glebov, A. N.

AU - Kostochka, A. V.

AU - Tashkinov, V. A.

PY - 2005/2/28

Y1 - 2005/2/28

N2 - 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.

AB - 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.

KW - List coloring

KW - Planar graphs

KW - Triangle-free graphs

UR - http://www.scopus.com/inward/record.url?scp=14544295303&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=14544295303&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2004.10.015

DO - 10.1016/j.disc.2004.10.015

M3 - Article

AN - SCOPUS:14544295303

SN - 0012-365X

VL - 290

SP - 269

EP - 274

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2-3

ER -

Smaller planar triangle-free graphs that are not 3-list-colorable

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this