Everyone is welcome to attend the N&O lecture of Ross Kang at CWI.
Abstract: Graph powers arise naturally in the study of, for example, efficient
network communication. Some basic problems have long been studied and
remain stubbornly open. I will first discuss previous work on the
chromatic number of graph powers, for graphs of maximum degree d,
often taking d very large. This is related to conjectures of Bollobás
and of Erdos and Nešetril from the 1980s. Then I will discuss
restricted versions where we impose an additional girth or cycle
length restriction. This relates to a problem of Alon and Mohar. This
is joint work with Francois Pirot.
