Colorings and list colorings of graphs and hypergraphs

In this thesis we study some extremal problems related to colorings and list colorings of graphs and hypergraphs. One of the main problems that we study is: What is the minimum number of edges in an $r$-uniform hypergraph that is not $t$-colorable ? This number is denoted by $m(r,t)$. We study it for general $r$-uniform hypergraphs and the corresponding parameter for simple hypergraphs. We also study a version of this problem for conflict-free coloring of hypergraphs. Finally, we also look into list coloring of complete graphs with some restrictions on the lists.\\ Let $t$ be a positive integer and $n=\lfloor \log_2 t\rfloor$. Generalizing earlier known bounds, we prove that there is a positive $\epsilon(t)$ such that for sufficiently large $r$, every $r$-uniform hypergraph with maximum edge degree at most $$ \epsilon(t)\, t^r \left(\frac{r}{\ln r}\right)^ {\frac{n}{n+1}}$$ is $t$-colorable. The above expression is also a lower bound for $m(r,t)$. \medskip A hypergraph is {\em $b$-simple} if no two distinct edges share more than $b$ vertices. Let { $m(r,t,g)$} denote the minimum number of edges in an { $r$-uniform} { non-$t$-colorable} hypergraph of girth at least $g$. Erd\H{o}s and Lov\'asz~\cite{EL} proved that $$m(r,t,3)\geq\frac{t^{2(r-2)}}{16r(r-1)^2}$$ $$\mbox{and}\quad m(r,t,g)\leq 4\cdot 20^{g-1} r^{3g-5} t^{(g-1)(r+1)}.$$ A result of Z.~Szab\'o~\cite{Szabo} improves the lower bound by a factor of $r^{2-\epsilon}$ for sufficiently large $r$. We improve the lower bound by another factor of $r$ and extend the result to $b$-simple hypergraphs. We also get a new lower bound for hypergraphs with a given girth. Our results imply that for fixed $b,t$ and $\epsilon$ and sufficiently large $r$, every $r$-uniform $b$-simple hypergraph $\mathcal{H}$ with maximum edge-degree at most $t^r r^{1-\epsilon}$ is $t$-colorable. Some results hold for list coloring, as well.\medskip We also study the same problem for conflict-free coloring. A coloring of the vertices of a hypergraph $\mathcal{H}$ is called $\textit{conflict-free}$ if each edge $e$ of $\mathcal{H}$ contains a vertex whose color does not get repeated in $e$. The smallest number of colors required for such a coloring is called the \textit{conflict-free chromatic number} of $\mathcal{H}$ and is denoted by $\chi_{CF}(\mathcal{H})$. Pach and Tardos studied this parameter for graphs and hypergraphs. Among other things, they proved that for a $(2r-1)$-uniform hypergraph $\mathcal{H}$ with $m$ edges, $\chi_{CF}(\mathcal{H})$ has the order $m^{1/r} \log m$. They also asked whether the same result holds for $r$-uniform hypergraphs. In this thesis we show that this is not necessarily true. Furthermore, we provide lower and upper bounds on the minimum number of edges in an $r$-uniform simple hypergraph that is not conflict-free $k$-colorable.\medskip Another topic we study is "choosability with separation" for complete graphs. For a graph $G$ and a positive integer $c$, let $\chi_{l}(G,c)$ be the minimum value of $k$ such that one can properly color the vertices of $G$ from any lists $L(v)$ such that $|L(v)|=k$ for all $v\in V(G)$ and $|L(u)\cap L(v)|\leq c$ for all $uv\in E(G)$. Kratochv\'il, Tuza and Voigt~\cite{KTV} asked to determine $\lim_{n\rightarrow \infty} \chi_{l}(K_n,c)/\sqrt{cn}$, if it exists. We prove that the limit exists and equals $1$. We also find the exact value of $\chi_{l}(K_n,c)$ for infinitely many values of $n$.\medskip Section $2$ deals with coloring of general hypergraphs. It is a joint work with A.~Kostochka and V.~R\"odl and appears in \cite{KKR}. Section $3$ deals with coloring of simple hypergraphsa. It is a joint work with A.~Kostochka and appears in \cite{KK}. In Section $4$, we study conflict-free coloring of hypergraphs and it is a joint work with A.~Kostochka and T.~{\L}uczak. It appears in \cite{KKL}. Section $5$ deals with separated list coloring of complete graphs. It is a joint work with Z.~F\"uredi and A.~Kostochka and appears in \cite{FKK}