ISGCI project home All classes SmallgraphsGraphclass: AT-free
Definition:
Three vertices of a graph form an asteroidal triple if every two of them are connected by a path avoiding the neighbourhood of the third.
A graph is AT-free
if it does not contain any asteroidal triple.
References:
[721]
[1098]
Equivalent classes:
(Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,X40,X41,XF2n+1,XF3n,XF4n)-free
Complement classes:
(co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X35),co-(X36),co-(X37),co-(X38),co-(X39),co-(X40),co-(X41),co-XF2n+1,co-XF3n,co-XF4n)-free
Related classes:
AT-free 
bipartite AT-free chordal AT-free claw-free astral triple-free diametral path dominating pair frame hereditary dominating pair
Inclusions
Minimal superclasses:
(6,1)-even-chordal (S3,S4,net)-free (S3,net)-free sun-free dominating pair even-hole-free
Maximal subclasses:
(2K2,C4,C5,S3,co-rising sun,net,rising sun)-free (A,E,S3,X1,domino,hole,house,net,rising sun)-free AT-free bipartite AT-free claw-free (C5,P,P5,co-(P),bull,co-gem,fork)-free (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,co-XF12n+3,co-XF52n+3,co-XF62n+2,odd anti-hole)-free (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd anti-hole)-free (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd-hole)-free (Cn+6,X37,claw,co-antenna,net,sun)-free P4-extendible P4-indifference (P5,bull,house)-free (P5,bull)-free (T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,anti-hole,co-XF12n+3,co-XF52n+3,co-XF62n+2,hole)-free (T2,X2,X3,hole,triangle)-free (X34,X36,XF2n+1,XF3n,co-(Cn+4),co-XF12n+3,co-XF62n+2)-free (XC7,co-(XC1),co-(XC2),co-(XC3),co-(XC4),co-(XC5),co-(XC6),co-(XC8))-free bipartite permutation bipartite tolerance bounded multitolerance chordal co-chordal co-comparability comparability circle graph with equator co-comparability co-comparability comparability co-comparability graphs of posets of interval dimension 2 co-interval interval co-permutation comparability graphs of dimension 2 posets containment graph of intervals permutation permutation split split threshold signed trapezoid unit tolerance
Problems summary
| Recognition: | Polynomial | details |
| Cliquewidth expression: |
Unbounded or NP-complete
| details |
| Cliquewidth: | Unbounded | details |
| Weighted independent set: | Polynomial | details |
| Independent set: | Polynomial | details |
| Domination: | Polynomial | details |
Algorithms for Recognition
Polynomial [O(n^2.83)]
[1214]
Algorithms for Cliquewidth expression
See also
: Cliquewidth : Weighted independent set : Domination
Algorithms for Cliquewidth
Unbounded from bipartite permutation
[1182]
Unbounded from (2K2,co-(C6),odd anti-cycle)-free
Unbounded from (C5,P,P5,co-(P),bull,co-gem,fork)-free
[1185]
Unbounded from co-comparability graphs of posets of interval dimension 2, height 1
Unbounded from permutation
[1177]
Unbounded from (3K1,co-(H))-free
Unbounded from unit interval
[1177]
Unbounded from (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(X85))-free
Unbounded from (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(K1,4),co-(X85))-free
Unbounded from co-bipartite
Unbounded from (3K1,co-cross)-free
Unbounded from (2K3,3K1,co-(A),co-(H),co-(X45))-free
Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free
See also
: Cliquewidth expression Algorithms for Weighted independent set
Polynomial [O(n^4)]
[160]
See also
: Cliquewidth expression : Independent set
Algorithms for Independent set
See also
: Weighted independent set
Algorithms for Domination
Polynomial
[1152]
See also
: Cliquewidth expression