Algorithms for Recognition
Polynomial from (1,2)-colorable
chordal
[1249]
Polynomial from (1,2)-colorable
chordal chordal chordal (2K3,house)-free (2K4,house)-free (3K3,Cn+4)-free HHDbicycle-free hereditary Matula perfect chordal (1,1)-colorable (1,2)-polar chordal (2K2,C4,C5,S3,net)-free (2K2,C4,C5)-free (2K3,2P3,C4,K3 
P3,P4)-free (2K3,2P3,Cn+4,K3 P3)-free (S3,net)-free split (T3,X81,cycle)-free bipartite bridged chordal co-chordal cycle-free probe interval tree split tree | Recognition: | Polynomial | details |
| Cliquewidth expression: | Unbounded or NP-complete | details |
| Cliquewidth: | Unbounded | details |
| Weighted independent set: | Linear | details |
| Independent set: | Linear | details |
| Domination: | NP-complete | details |
Algorithms for Recognition
Polynomial from (1,2)-colorable chordal
[1249]
Polynomial from (1,2)-colorable chordal
| From the constituent classes. |
Algorithms for Cliquewidth expression
See also
: Cliquewidth : Weighted independent set : Domination
Algorithms for Cliquewidth
Unbounded from split
[1176]
See also
: Cliquewidth expression
Algorithms for Weighted independent set
Linear from chordal
[1166]
Polynomial from (K2,3,P,hole)-free
[1107]
Polynomial from interval filament
[1159]
Polynomial [O(n^{6p+2})]
from (p,q<=2)-colorable
[1116]
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 Meyniel
[169]
Polynomial from clique separable
[1081]
See also
: Weighted independent set
Algorithms for Domination
NP-complete from split
[1144]
[1145]
See also
: Cliquewidth expression