2010 seminar talk: Measurable colorings of graphs, I

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


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.

Bottom menu

Kurt Gödel Research Center for Mathematical Logic. Währinger Straße 25, 1090 Wien, Austria. Phone +43-1-4277-50501. Last updated: 2010-12-16, 04:37.