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


Henning Bruhn
Clique or hole in claw-free graphs

Coauthor: Akira Saito


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" [...]


  Payday Loans In Ohio. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.