Colorings and list colorings of graphs and hypergraphs

Graph Coloring;List Coloring;Hypergraphs

Kumbhat, Mohit

关键词: Graph Coloring;    List Coloring;    Hypergraphs;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/30921/kumbhat_mohit.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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)$. \medskipA 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 inan { $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}$ forsufficiently 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.\medskipWe 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 weshow 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.\medskipAnother 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$.\medskipSection $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 ofhypergraphs 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}.