Choosability and paintability of the lexicographic product of graphs

被引：0

作者：

Keszegh, Balazs ^{[1
]}

Zhu, Xuding ^{[2
]}

机构：

[1] Alfred Renyi Inst Math, POB 127, H-1364 Budapest, Hungary

[2] Zhejiang Normal Univ, Dept Math, Jinhua, Zhejiang, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2017年 / 223卷

关键词：

List coloring; Choice number; On-line choosability; Paintability; Game coloring; Lexicographic product;

D O I：

10.1016/j.dam.2017.02.008

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper studies the choice number and paint number of the lexicographic product of graphs. We prove that if G has maximum degree 4, then for any graph H on n vertices ch(G[H]) <= (4 triangle + 2)(ch(H) + log(2) n) and X-p(G[H]) <= (4 triangle + 2)(X-P(1-1) + log(2) n). (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：84 / 90

页数：7

共 13 条

[1] Choosability and fractional chromatic numbers [J].

Alon, N ;

Tuza, Z ;

Voigt, M .

DISCRETE MATHEMATICS, 1997, 165 :31-38

[2]

Alon N., 1992, COMB PROBAB COMPUT, V1, P107, DOI [DOI 10.1017/S0963548300000122, 10.1017/S09635483000, 10.1017/S0963548300000122]

[3]

Borowiecki M., 2007, ELECTRON J COMB, V14, P26

[4] ON-LINE 3-CHOOSABLE PLANAR GRAPHS [J].

Chang, Ting-Pang ;

Zhu, Xuding .

TAIWANESE JOURNAL OF MATHEMATICS, 2012, 16 (02) :511-519

[5]

Duraj L., 2011, PREPRINT

[6]

Erdos P., 1979, C NUMERANTUM, V26, P125

[7] CHROMATIC NUMBER AND OTHER FUNCTIONS OF LEXICOGRAPHIC PRODUCT [J].

GELLER, D ;

STAHL, S .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 19 (01) :87-95

[8]

Gutowski G., 2011, Electron. J. Combin, V18, P8

[9]

SCHAUZ U, 2010, ELECTRON J COMB, V17, P18

[10]

Schauz Uwe, 2009, Electron. J. Combin., V16, P18

← 1 2 →