Kurt Gödel Research Center

2010 seminar talk: Measurable colorings of graphs, I

Talk held by Clinton Conley (KGRC) at the KGRC seminar on 2010-11-04.

Abstract

We discuss how the study of graph colorings changes when definability restrictions are placed upon the coloring functions. In this talk, we focus on "positive" results, i.e., reworking classical (nondescriptive) theorems to fit into this context. In particular, we analyze colorings of hyperfinite graphs and also study the Brooks bound: the chromatic number of a graph is at most the maximum degree of a vertex. This is joint work with Alekos Kechris.