A GENERAL FRAMEWORK FOR HYPERGRAPH COLORING

被引:10
作者
Wanless, Ian M. [1 ]
Wood, David R. [1 ]
机构
[1] Monash Univ, Sch Math, Clayton, Vic 3800, Australia
基金
澳大利亚研究理事会;
关键词
hypergraph; coloring; local lemma; LOVASZ LOCAL LEMMA; INDEPENDENT TRANSVERSALS; NUMBER;
D O I
10.1137/21M1421015
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The Lovasz Local Lemma is a powerful probabilistic technique for proving the existence of combinatorial objects. It is especially useful for coloring graphs and hypergraphs with bounded maximum degree. This paper presents a general theorem for coloring hypergraphs that in many instances matches or slightly improves upon the bounds obtained using the Lovasz Local Lemma. Moreover, the theorem directly shows that there are exponentially many colorings. The elementary and self-contained proof is inspired by a recent result for nonrepetitive colorings by Rosenfeld [Electron. J. Combin., 27 (2020), P3.43]. We apply our general theorem in the settings of proper hypergraph coloring, proper graph coloring, independent transversals, star coloring, nonrepetitive coloring, frugal coloring, Ramsey number lower bounds, and k-SAT.
引用
收藏
页码:1663 / 1677
页数:15
相关论文
共 69 条
[1]   Colorings of hypergraphs with large number of colors [J].
Akolzin, Ilia ;
Shabanov, Dmitry .
DISCRETE MATHEMATICS, 2016, 339 (12) :3020-3031
[2]   Nonrepetitive colorings of graphs [J].
Alon, N ;
Grytczuk, J ;
Haluszcak, M ;
Riordan, O .
RANDOM STRUCTURES & ALGORITHMS, 2002, 21 (3-4) :336-346
[3]   PROBABILISTIC METHODS IN COLORING AND DECOMPOSITION PROBLEMS [J].
ALON, N .
DISCRETE MATHEMATICS, 1994, 127 (1-3) :31-46
[4]   EVERY 8-UNIFORM 8-REGULAR HYPERGRAPH IS 2-COLORABLE [J].
ALON, N ;
BREGMAN, Z .
GRAPHS AND COMBINATORICS, 1988, 4 (04) :303-305
[5]  
Alon N., 1985, Graphs and Combinatorics, V1, P387, DOI 10.1007/BF02582966
[6]   Entropy compression versus Lovasz Local Lemma [J].
Alves, Rogerio G. ;
Procacci, Aldo ;
Sanchis, Remy .
ADVANCES IN APPLIED MATHEMATICS, 2021, 125
[7]  
Aprile M. F., 2014, THESIS U OXFORD
[8]   3-CHROMATIC HYPERGRAPHS [J].
BECK, J .
DISCRETE MATHEMATICS, 1978, 24 (02) :127-137
[9]  
Bernshteyn A, 2015, Arxiv, DOI arXiv:1410.1591
[10]  
Bernshteyn A, 2022, Arxiv, DOI arXiv:2109.13376