2015 seminar talk: Trees, ladders and graphs

Talk held by Daniel Soukup (University of Toronto, Canada) at the KGRC seminar on 2015-01-15.


The chromatic number of a graph $G$ is the least (cardinal) number $\kappa$ such that the vertices of $G$ can be covered by $\kappa$ many independent sets. A fundamental problem of graph theory asks how large chromatic number affects structural properties of a graph and in particular, is it true that a graph with large chromatic number has certain obligatory subgraphs? The aim of this talk is to introduce a new and rather flexible method to construct uncountably chromatic graphs from non special trees and ladder systems. Answering a question of P. Erdős and A. Hajnal, we construct graphs of chromatic number $\omega_1$ without uncountable infinitely connected subgraphs.

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.