TY - JOUR
T1 - DP-colorings of hypergraphs
AU - Bernshteyn, Anton
AU - Kostochka, Alexandr
N1 - Publisher Copyright:
© 2019 Elsevier Ltd
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2019/5
Y1 - 2019/5
N2 - Classical problems in hypergraph coloring theory are to estimate the minimum number of edges, m 2 (r) (respectively, m 2 ∗ (r)), in a non-2-colorable r-uniform (respectively, r-uniform and simple) hypergraph. The best currently known bounds are c⋅r∕logr⋅2 r ⩽m 2 (r)⩽C⋅r 2 ⋅2 r andc ′ ⋅r −ε ⋅4 r ⩽m 2 ∗ (r)⩽C ′ ⋅r 4 ⋅4 r ,for any fixed ε>0 and some c, c ′ , C, C ′ >0 (where c ′ may depend on ε). In this paper we consider the same problems in the context of DP-coloring (also known as correspondence coloring), which is a generalization of list coloring introduced by Dvořák and Postle and related to local conflict coloring studied independently by Fraigniaud, Heinrich, and Kosowski. Let m˜ 2 (r) (respectively, m˜ 2 ∗ (r)) denote the minimum number of edges in a non-2-DP-colorable r-uniform (respectively, r-uniform and simple) hypergraph. By definition, m˜ 2 (r)⩽m 2 (r) and m˜ 2 ∗ (r)⩽m 2 ∗ (r). While the proof of the bound m 2 ∗ (r)=Ω(r −3 4 r ) due to Erdős and Lovász also works for m˜ 2 ∗ (r), we show that the trivial lower bound m˜ 2 (r)⩾2 r−1 is asymptotically tight, i.e., m˜ 2 (r)⩽(1+o(1))2 r−1 . On the other hand, when r⩾2 is even, we prove that the lower bound m˜ 2 (r)⩾2 r−1 is not sharp, i.e., m˜ 2 (r)⩾2 r−1 +1. Whether this result holds for infinitely many odd values of r remains an open problem. Nevertheless, we conjecture that the difference m˜ 2 (r)−2 r−1 can be arbitrarily large.
AB - Classical problems in hypergraph coloring theory are to estimate the minimum number of edges, m 2 (r) (respectively, m 2 ∗ (r)), in a non-2-colorable r-uniform (respectively, r-uniform and simple) hypergraph. The best currently known bounds are c⋅r∕logr⋅2 r ⩽m 2 (r)⩽C⋅r 2 ⋅2 r andc ′ ⋅r −ε ⋅4 r ⩽m 2 ∗ (r)⩽C ′ ⋅r 4 ⋅4 r ,for any fixed ε>0 and some c, c ′ , C, C ′ >0 (where c ′ may depend on ε). In this paper we consider the same problems in the context of DP-coloring (also known as correspondence coloring), which is a generalization of list coloring introduced by Dvořák and Postle and related to local conflict coloring studied independently by Fraigniaud, Heinrich, and Kosowski. Let m˜ 2 (r) (respectively, m˜ 2 ∗ (r)) denote the minimum number of edges in a non-2-DP-colorable r-uniform (respectively, r-uniform and simple) hypergraph. By definition, m˜ 2 (r)⩽m 2 (r) and m˜ 2 ∗ (r)⩽m 2 ∗ (r). While the proof of the bound m 2 ∗ (r)=Ω(r −3 4 r ) due to Erdős and Lovász also works for m˜ 2 ∗ (r), we show that the trivial lower bound m˜ 2 (r)⩾2 r−1 is asymptotically tight, i.e., m˜ 2 (r)⩽(1+o(1))2 r−1 . On the other hand, when r⩾2 is even, we prove that the lower bound m˜ 2 (r)⩾2 r−1 is not sharp, i.e., m˜ 2 (r)⩾2 r−1 +1. Whether this result holds for infinitely many odd values of r remains an open problem. Nevertheless, we conjecture that the difference m˜ 2 (r)−2 r−1 can be arbitrarily large.
UR - http://www.scopus.com/inward/record.url?scp=85061918055&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85061918055&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2019.01.011
DO - 10.1016/j.ejc.2019.01.011
M3 - Article
AN - SCOPUS:85061918055
VL - 78
SP - 134
EP - 146
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
SN - 0195-6698
ER -