On claw-free asteroidal triple-free graphs

AbstractWe present an O(n2.376) algorithm for recognizing claw-free AT-free graphs and a linear-time algorithm for computing the set of all central vertices of a claw-free AT-free graph. In addition, we give efficient algorithms that solve the problems INDEPENDENT SET, DOMINATING SET, and COLORING. We argue that all running times achieved are optimal unless better algorithms for a number of famous graph problems such as triangle recognition and bipartite matching have been found. Our algorithms exploit the structure of 2LexBFS schemes of claw-free AT-free graphs