[home] - [up] |
Abstract: Graph coloring is a central but hard to tackle topic in discrete mathematics and combinatorial optimization. In particular, it is still unresolved how to obtain good lower bounds on the chromatic number of a graph. (To be more precise, all the known lower bounds are either rather weak, not computable, or work only in specific cases.)
In the topological approach to graph coloring problems, initiated 1978 by Lovasz' proof of the Kneser conjecture, lower bounds on the chromatic number are obtained by associating certain simplicial or cell complexes to a graph and then exploiting topological invariants of the resulting spaces (whenever this is possible).
An exposition of Lovasz' approach will be given in the talk. Also we will discuss the geometric, topological, and combinatorial properties of some interesting classes of coloring complexes.
Colloquium - 16:00
Abstract: We consider a random graph process where edges are added randomly, subject to the condition that the graph remains triangle-free. We study various properties that the resulting maximal triangle-free graph will have with high probability. One of the questions we would like to answer is which (triangle-free) graphs will almost surely appear as subgraphs - and when this happens.