ISGCI project home  All classes  Smallgraphs

Graphclass: (1,2)-polar cap chordal

References: [1254]
Equivalent classes:  (2K3,2P3,Cn+4,K3 cup P3)-free 
Complement classes:  (K3,3,K3,3+e,co-(2P3),co-(Cn+4))-free 
Related classes:  (1,2)-polar   chordal 

Inclusions

Minimal superclasses:  (1,2)-colorable cap chordal   (1,2)-polar   (2K3,2P3,C5,C6,C7,K2,3,K3 cup P3,X84,co-(3K2),co-(C4 cup P2),co-(C6),co-(P2 cup P4),co-(P6),co-(X18),co-(X5),co-antenna,co-domino,co-fish)-free   (2K3,Cn+4)-free   (C6,K3,3+e,P,P7,X37,X41)-free   HHDbicycle-free   (P,P8)-free   hereditary Matula perfect 
Maximal subclasses:  (1,1)-colorable   (2K2,C4,C5,S3,net)-free   (2K2,C4,C5)-free   (2K3,2P3,C4,K3 cup P3,P4)-free   (S3,net)-free cap split   chordal cap co-chordal   split 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:Lineardetails
Independent set:Lineardetails
Domination:NP-completedetails

Algorithms for Recognition


Polynomial
     From the constituent classes.


Polynomial
     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 [O(V^8)] from (P,P7)-free  [1351]
Polynomial from (C6,K3,3+e,P,P7,X37,X41)-free  [1346]
Polynomial from Meyniel  [169]
Polynomial from clique separable  [1081]
Polynomial from (P,star1,2,5)-free  [1349]
Polynomial from (P,P8)-free  [1306]
Open from (P,star1,2,4)-free  [1351] [1306]
See also : Weighted independent set

Algorithms for Domination

NP-complete from split  [1144] [1145]
See also : Cliquewidth expression