ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 05C35, 05C75 Brandt, Stephan, Freie Universität Berlin, Germany Pach’s Theorem on triangle-free graphs revisited. In a triangle-free graph, the neighbourhood of every vertex forms an independent set. In 1981, Pach characterized the triangle-free graphs, in which every independent set is contained in the neighbourhood of a vertex. In the talk, a forbidden subgraph characterization of these graphs is presented, as well as several surprising applications of the new characterization.