On a list coloring conjecture of Reed

被引：14

作者：

Bohman, T ^{[1
]}

Holzman, R

机构：

[1] Technion Israel Inst Technol, Dept Math, IL-32000 Haifa, Israel

[2] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

来源：

JOURNAL OF GRAPH THEORY | 2002年 / 41卷 / 02期

关键词：

list coloring; choosability; vetrtex-color degree;

D O I：

10.1002/jgt.10054

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We construct graphs with lists of available colors for each vertex, such that the size of every list exceeds the maximum vertex-color degree, but there exists no proper coloring from the lists. This disproves a conjecture of Reed. (C) 2002 Wiley Periodicals, Inc.

引用

页码：106 / 109

页数：4

共 50 条

[1] Equitable list coloring of graphs
Wang, WF
Lih, KW
TAIWANESE JOURNAL OF MATHEMATICS, 2004, 8 (04): : 747 - 759
[2] List Coloring with a Bounded Palette
Bonamy, Marthe
Kang, Ross J.
JOURNAL OF GRAPH THEORY, 2017, 84 (01) : 93 - 103
[3] Between coloring and list-coloring: μ-coloring
Bonomo, Flavia
Cecowski Palacio, Mariano
ARS COMBINATORIA, 2011, 99 : 383 - 398
[4] List coloring digraphs
Bensmail, Julien
Harutyunyan, Ararat
Ngoc Khang Le
JOURNAL OF GRAPH THEORY, 2018, 87 (04) : 492 - 508
[5] List coloring with requests
Dvorak, Zdenek
Norin, Sergey
Postle, Luke
JOURNAL OF GRAPH THEORY, 2019, 92 (03) : 191 - 206
[6] Criticality, the list color function, and list coloring the cartesian product of graphs
Kaul, Hemanshu
Mudrock, Jeffrey A.
JOURNAL OF COMBINATORICS, 2021, 12 (03) : 479 - 514
[7] A note on list-coloring powers of graphs
Kosar, Nicholas
Petrickova, Sarka
Reiniger, Benjamin
Yeager, Elyse
DISCRETE MATHEMATICS, 2014, 332 : 10 - 14
[8] Hajos' theorem for list coloring
Král, D
DISCRETE MATHEMATICS, 2004, 287 (1-3) : 161 - 163
[9] Equitable List Coloring and Treewidth
Pelsmajer, Michael J.
JOURNAL OF GRAPH THEORY, 2009, 61 (02) : 127 - 139
[10] A list analogue of equitable coloring
Kostochka, AV
Pelsmajer, MJ
West, DB
JOURNAL OF GRAPH THEORY, 2003, 44 (03) : 166 - 177

← 1 2 3 4 5 →