Flexibility of planar graphs of girth at least six

被引：5

作者：

Dvorak, Zdenek ^{[1
]}

Masarik, Tomas ^{[2
]}

Musilek, Jan ^{[2
]}

Pangrac, Ondrej ^{[1
]}

机构：

[1] Charles Univ Prague, CSI, Malostranske Namesti 25, Prague 11800, Czech Republic

[2] Charles Univ Prague, Dept Appl Math, Prague, Czech Republic

来源：

JOURNAL OF GRAPH THEORY | 2020年 / 95卷 / 03期

关键词：

coloring; flexibility; girth six; planar graph;

D O I：

10.1002/jgt.22567

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G has girth at least six and all lists have size at least three, then there exists an L-coloring respecting at least a constant fraction of the preferences.

引用

页码：457 / 466

页数：10

共 8 条

[1]

DVORAK Z, 2017, 190202971 ARXIV

[2] List coloring with requests [J].

Dvorak, Zdenek ;

Norin, Sergey ;

Postle, Luke .

JOURNAL OF GRAPH THEORY, 2019, 92 (03) :191-206

[3]

Dvorák Z, 2017, ELECTRON J COMB, V24

[4]

Erdo P., 1979, Congr. Numer., V26, P125

[5] Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces [J].

Postle, Luke .

2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), 2019, :929-941

[6] 3-LIST-COLORING PLANAR GRAPHS OF GIRTH-5 [J].

THOMASSEN, C .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 64 (01) :101-107

[7] A NOT 3-CHOOSABLE PLANAR GRAPH WITHOUT 3-CYCLES [J].

VOIGT, M .

DISCRETE MATHEMATICS, 1995, 146 (1-3) :325-328

[8] LIST COLORINGS OF PLANAR GRAPHS [J].

VOIGT, M .

DISCRETE MATHEMATICS, 1993, 120 (1-3) :215-219

← 1 →