Files in this item
Files  Description  Format 

application/pdf kumbhat_mohit.pdf (502kB)  (no description provided)  
application/postscript config1.eps (12kB)  (no description provided)  Postscript 
Description
Title:  Colorings and list colorings of graphs and hypergraphs 
Author(s):  Kumbhat, Mohit 
Director of Research:  Kostochka, Alexandr V. 
Doctoral Committee Chair(s):  Furedi, Zoltan 
Doctoral Committee Member(s):  Kostochka, Alexandr V.; West, Douglas B.; Balogh, József 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
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 conflictfree 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(r2)}}{16r(r1)^2}$$ $$\mbox{and}\quad m(r,t,g)\leq 4\cdot 20^{g1} r^{3g5} t^{(g1)(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 edgedegree 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 conflictfree coloring. A coloring of the vertices of a hypergraph $\mathcal{H}$ is called $\textit{conflictfree}$ 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{conflictfree 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 $(2r1)$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 conflictfree $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 conflictfree 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:  20120522 
URI:  http://hdl.handle.net/2142/30921 
Rights Information:  Copyright 2012 Mohit Kumbhat 
Date Available in IDEALS:  20120522 
Date Deposited:  201205 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics