Asteroidal triple-free graph
In graph theory, an asteroidal triple-free graph or AT-free graph is a graph that contains no asteroidal triple.
Definition
An asteroidal triple is an independent set of three vertices such that each pair is joined by a path that avoids the neighborhood of the third vertex. More formally, in a graph, three vertices,, and form an asteroidal triple if:- , and are pairwise non-adjacent
- There exists an -path that avoids
- There exists an -path that avoids
- There exists a -path that avoids
Relationship to other graph classes
AT-free graphs provide a common generalization of several important graph classes:- Interval graphs are precisely the graphs that are both chordal and AT-free.
- Permutation graphs are AT-free.
- Trapezoid graphs are AT-free.
- Cocomparability graphs are AT-free.
Structural properties
Characterizations
AT-free graphs can be characterized in multiple ways:- Via minimal triangulations: A graph is AT-free if and only if every minimal triangulation of is an interval graph. Additionally, a claw-free AT-free graph is characterized by the property that all of its minimal chordal completions are proper interval graphs.
- Via unrelated vertices: A graph is AT-free if and only if for every vertex of, no component of the non-neighborhood of contains vertices that are unrelated with respect to.
- Via dominating pairs and the spine property.
Dominating pairs
Every connected AT-free graph contains a dominating pair, a pair of vertices such that every path joining them is a dominating set in the graph.Furthermore, some dominating pair achieves the diameter of the graph. Every connected AT-free graph has a path-mccds. In AT-free graphs with diameter at least 4, the vertices that can be in dominating pairs are restricted to two disjoint sets and, where is a dominating pair if and only if and.
Spine property
A graph is AT-free if and only if every connected induced subgraph satisfies the spine property: for every nonadjacent dominating pair in, there exists a neighbor of such that is a dominating pair in the component of containing.Decomposition
AT-free graphs admit a decomposition scheme through pokable dominating pairs. A vertex is pokable if adding a pendant vertex adjacent to preserves the AT-free property. Every connected AT-free graph contains a pokable dominating pair, and contracting certain equivalence classes of vertices yields another AT-free graph with a pokable dominating pair. This process can be repeated until the graph is reduced to a single vertex.Algorithmic properties
AT-free graphs can be recognized in time for an -vertex graph.For AT-free graphs, the pathwidth equals the treewidth.
The strong perfect graph theorem holds for AT-free graphs, as they are a subclass of perfect graphs.