Files in this item



application/pdfKantor_Ida.pdf (588kB)
(no description provided)PDF


Title:Graphs, codes, and colorings
Author(s):Kantor, Ida
Director of Research:Furedi, Zoltan
Doctoral Committee Chair(s):West, Douglas B.
Doctoral Committee Member(s):Furedi, Zoltan; Kostochka, Alexandr V.; Reznick, Bruce A.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):sum choice number
list coloring
product dimension
graph representation
Abstract:\noindent{This thesis focuses on topics in extremal combinatorics.} Given an integer-valued function $f$ defined on the vertices of a graph $G$, we say $G$ is {\em $f$-choosable} if for every collection of lists with list sizes specified by $f$ there is a proper coloring using the colors from the lists. The {\em sum choice number}, $\chi_{sc}(G)$, is the minimum of $\sum f(v)$ such that $G$ is $f$-choosable. We show that if $q\geq 4 a^2\log a$, then there exist constants $c_1$ and $c_2$ such that \[ 2q+c_1a\sqrt{q\log {a}}\leq \chi_{\rm sc}(K_{a,q})\leq 2q+c_2a\sqrt{q\log {a}}.\] As a consequence, $\chi_{sc}(G)/|V(G)|$ can be bounded while the minimum degree $\delta_{\rm min}(G)\to \infty$. This is not true for the list chromatic number, $\chi_\ell(G)$. We further prove that, for fixed $a$, the limit $\lim_{q\to \infty} (\chi_{\rm sc}(K_{a,q})-2q)/\sqrt{q}$ exists, and we give tight bounds for sum choice numbers of the graphs $G_{a,q}$, which are obtained from $K_{a,q}$ by adding all possible edges in the part of size $a$. A pair of ordered $k$-tuples $(x_1,...,x_k)$, $(y_1,...,y_k)$ is {\em reverse-free} if, for all $i
Issue Date:2011-01-14
Rights Information:Copyright 2010 Ida Kantor. SIAM holds the copyright to part of the work included in Chapter 2 of the thesis, since it was published in a SIAM journal.
Date Available in IDEALS:2011-01-14
Date Deposited:December 2

This item appears in the following Collection(s)

Item Statistics