Asteroidal

Algorithms for asteroidal triples and asteroidal numbers in graphs.

An asteroidal triple in a graph G is a set of three non-adjacent vertices u, v and w such that there exist a path between any two of them that avoids closed neighborhood of the third. More formally, v_j, v_k belongs to the same connected component of G - N[v_i], where N[v_i] denotes the closed neighborhood of v_i. A graph which does not contain any asteroidal triples is called an AT-free graph. The class of AT-free graphs is a graph class for which many NP-complete problems are solvable in polynomial time. Amongst them, independent set and coloring.

is_at_free(G)	Check if a graph is AT-free.
find_asteroidal_triple(G)	Find an asteroidal triple in the given graph.