## Files in this item

FilesDescriptionFormat

application/pdf

Kantor_Ida.pdf (588kB)
(no description provided)PDF

## 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 Urbana-Champaign 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 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 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: 2011-01-14 Date Deposited: December 2
﻿