IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Colorings and list colorings of graphs and hypergraphs

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/30921

Files in this item

File Description Format
PDF kumbhat_mohit.pdf (502KB) (no description provided) PDF
Postscript config1.eps (12KB) (no description provided) Postscript
Title: Colorings and list colorings of graphs and hypergraphs
Author(s): Kumbhat, Mohit
Director of Research: Kostochka, Alexander V.
Doctoral Committee Chair(s): Furedi, Zoltan
Doctoral Committee Member(s): Kostochka, Alexander V.; West, Douglas B.; Balogh, József
Department / Program: Mathematics
Discipline: Mathematics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(s): Graph Coloring List Coloring Hypergraphs
Abstract: 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}.
Issue Date: 2012-05-22
URI: http://hdl.handle.net/2142/30921
Rights Information: Copyright 2012 Mohit Kumbhat
Date Available in IDEALS: 2012-05-22
Date Deposited: 2012-05
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 153
  • Downloads this Month: 1
  • Downloads Today: 0

Browse

My Account

Information

Access Key