Combinatorics Seminar
Jacques Verstraete
UC San Diego
Injective labelings of graphs
Abstract: Abstract: In this talk I will discuss the problem of coloring the vertices of a graph with $k$ colors such that the neighborhood
$N(v)$ contains all $k$ colors for every vertex $v$ in the graph. The problem is to maximize the value of $k$ for which
such a coloring is possible. We show that if $G$ is a $d$-regular graph, then the maximum is $k = (1 + o(1))d/log d$
and that almost every d-regular graph required at least $(1 + o(1))d/log d$ colors. This problem has connections
to coding theory, and with this in mind we discuss colorings of the $q$-ary Hamming cube graphs of dimension $n$.
Some open problems will be given.
Joint work with Bob Chen, Jeong Han Kim and Mike Tait
Monday March 9, 2015 at 3:00 PM in SEO 427