Choosability with Separation of Complete Multipartite Graphs and Hypergraphs

被引：13

作者：

Fueredi, Zoltan ^{[1
,2
]}

Kostochka, Alexandr ^{[1
,3
]}

Kumbhat, Mohit ^{[4
]}

机构：

[1] Univ Illinois, Urbana, IL 61801 USA

[2] Hungarian Acad Sci, Renyi Inst Math, Budapest, Hungary

[3] Sobolev Inst Math, Novosibirsk, Russia

[4] Sungkyunkwan Univ, Suwon, South Korea

来源：

JOURNAL OF GRAPH THEORY | 2014年 / 76卷 / 02期

基金：

美国国家科学基金会; 俄罗斯基础研究基金会; 欧洲研究理事会;

关键词：

05C15; hypergraphs; separation; multipartite graphs; list coloring;

D O I：

10.1002/jgt.21754

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For a hypergraph G and a positive integer s, let chi l(G,s) be the minimum value of l such that G is L-colorable from every list L with |L(v)|=l for each v is an element of V(G) and |L(u)boolean AND L(v)|<= s for all u,v is an element of e is an element of E(G). This parameter was studied by Kratochvil, Tuza, and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of chi l(G,s) for balanced complete multipartite graphs and for complete k-partite k-uniform hypergraphs.

引用

页码：129 / 137

页数：9

共 9 条

[1]

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

[2]

[Anonymous], ELECT J COMBIN

[3]

[Anonymous], P W COAST C COMB GRA

[4]

[Anonymous], ARXIV13034030

[5]

Erdos P., 1964, ACTA MATH ACAD SCI H, V15, P445, DOI DOI 10.1007/BF01897152

[6] On the asymptotic value of the choice number of complete multi-partite graphs [J].

Gazit, N ;

Krivelevich, M .

JOURNAL OF GRAPH THEORY, 2006, 52 (02) :123-134

[7]

Kratochvil J, 1998, J GRAPH THEOR, V27, P43

[8] RATIO OF OPTIMAL INTEGRAL AND FRACTIONAL COVERS [J].

LOVASZ, L .

DISCRETE MATHEMATICS, 1975, 13 (04) :383-390

[9]

Vizing V.G., 1976, Diskret. Analiz, P3

← 1 →