Graphs, codes, and colorings
Ida Kantor · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 2010
\ oindent{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