Forbidden paths

ACO Colloquium
Thursday, March 18, 2010 - 16:30
1 hour (actually 50 minutes)
Skiles 255
Charles University, Prague

***Refreshments at 4PM in Skiles 236.***

Forbidding (undirected or directed) paths in graphs, what can be easier? Yet we show that in the context of coloring problems (CSP) and structural graph theory, this is related to the notions tree depth, (restricted) dualities, bounded expansion and nowhere dense classes with applications both in and out of combinatorics.