**Monday, 16:15 - 16:40 h, Room: H 3005**

**Henning Bruhn**

Clique or hole in claw-free graphs

**Coauthor: Akira Saito**

**Abstract:**

Given a claw-free graph and two non-adjacent vertices *x* and *y* without common neighbours we prove that there exists a hole through *x* and *y* unless the graph contains the obvious obstruction, namely a clique separating *x* from *y*. As applications we derive an algorithm to verify whether there is a hole through two given vertices as well as an algorithm for the *3*-in-a-tree problem in claw-free graphs.

Talk 3 of the invited session Mon.3.H 3005

**"Exact and approximation algorithms on graphs"** [...]

Cluster 2

**"Combinatorial optimization"** [...]