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.
Trees, ladders and graphs
15.01.2015 15:00 - 16:30
Organiser:
KGRC
Location:
SR 101, 2. St., Währinger Str. 25