dominating pair dominating pair diametral path dominating pair chordal (2K2,C4,C5,S3,net)-free (2K2,C4,C5,co-sun)-free (3K1,C4,C5)-free AT-free chordal (C4,P4,dart)-free (C4,P4)-free (C4,odd anti-cycle)-free C4-free co-comparability (Cn+4,S3 
K1,claw,net)-free (Cn+4,T2,X31,XF2n+1,XF3n)-free (Cn+4,claw,net)-free (S3,net)-free split boxicity 1 chordal (claw,net)-free chordal co-comparability chordal cograph chordal proper circular arc cograph interval comparability graphs of arborescence orders intersection graph of nested intervals interval quasi-threshold superfragile trivially perfect | Recognition: | Polynomial | details |
| Cliquewidth expression: | Unbounded or NP-complete | details |
| Cliquewidth: | Unbounded | details |
| Weighted independent set: | Linear | details |
| Independent set: | Linear | details |
| Domination: | Unknown to ISGCI | details |
Algorithms for Recognition
Polynomial
[1292]
Algorithms for Cliquewidth expression
See also
: Cliquewidth : Weighted independent set : Domination
Algorithms for Cliquewidth
Unbounded from unit interval
[1177]
See also
: Cliquewidth expression
Algorithms for Weighted independent set
Linear from chordal
[1166]
Polynomial from (C4,C5,T2)-free
[1108]
Polynomial from (K2,3,P,hole)-free
[1107]
Polynomial from interval filament
[1159]
Polynomial from perfect
[476]
Polynomial [O(V^4)]
from weakly chordal
[997]
Polynomial from subtree overlap
[1123]
See also
: Cliquewidth expression : Independent set
Algorithms for Independent set
Linear from chordal
[425]
[931]
Polynomial from Gallai
[1081]
Polynomial [O(VE)]
from weakly chordal
[530]
[1119]
Polynomial from (P,T2)-free
[1305]
Polynomial from Meyniel
[169]
Polynomial from clique separable
[1081]
See also
: Weighted independent set
Algorithms for Domination
See also
: Cliquewidth expression