## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 134-146 |

Number of pages | 13 |

Journal | European Journal of Combinatorics |

Volume | 78 |

DOIs | |

State | Published - May 2019 |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics