Files in this item
Files  Description  Format 

application/pdf Kantor_Ida.pdf (588kB)  (no description provided) 
Description
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 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  sum choice number
list coloring product dimension graph representation codes 
Abstract:  \noindent{This thesis focuses on topics in extremal combinatorics.}
Given an integervalued 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 reversefree}
if, for all $i 
Issue Date:  20110114 
URI:  http://hdl.handle.net/2142/18247 
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:  20110114 
Date Deposited:  December 2 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics
Item Statistics
 Total Downloads: 250
 Downloads this Month: 13
 Downloads Today: 0