A non-3-choosable planar graph without cycles of length 4 and 5

被引：18

作者：

Voigt, M. ^{[1
]}

机构：

[1] Univ Appl Sci, D-01069 Dresden, Germany

来源：

DISCRETE MATHEMATICS | 2007年 / 307卷 / 7-8期

关键词：

choosability; planar graphs; forbidden cycles;

D O I：

10.1016/j.disc.2005.11.041

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Steinberg's question from 1975 whether every planar graph without 4- and 5-cycles is 3-colorable is still open. In this paper the analogous question for 3-choosability of such graphs is answered to the negative. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：1013 / 1015

页数：3

共 10 条

[1]

ABBOTT HL, 1991, ARS COMBINATORIA, V32, P203

[2]

[Anonymous], 1995, WILEY INTERSCIENCE S

[3]

Borodin OV, 1996, J GRAPH THEOR, V21, P183

[4] A sufficient condition for planar graphs to be 3-colorable [J].