Title: ON ORDERINGS OF UNDIRECTED GRAPHS
Lecturer: Jaroslav NESETRIL
Charles University Prague
Many extremal problems can be defined by means of the xistence of specialorderings. In the lecture we concentrate on two such problems both relatedto forbidden orderings and ordering theorems which originated in Ramseytheory.
First we show that there are sparse graphs with unavoidable orderings.Secondly we show surprising power of the corresponding decision problem:there is no dichotomy for the forbidden graph-ordering problem.