ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,co-(X91),co-claw)-free

Complement classes:  (C4,X91,claw)-free 
See also: co-(X91) co-claw 2K2

Inclusions

Minimal superclasses:  2K2-free   (P5,co-fork)-free   (co-(W4),co-claw)-free 
Maximal subclasses:  (2K2,C5,triangle)-free   (2K2,odd-cycle)-free   2K2-free cap bipartite   (S3,co-(Cn+4),co-(S3 cup K1),co-claw)-free   (S3,co-(Cn+4),co-claw,net)-free   (S3,co-(Cn+4),co-claw)-free   (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free   (co-(Cn+4),co-claw,co-gem,house)-free   co-(P3)-free   bipartite chain   difference 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:Polynomialdetails
Independent set:Polynomialdetails
Domination: Unknown to ISGCI details

Algorithms for Recognition

Polynomial
     Finite forbidden subgraph characterization


Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth



Unbounded
     From the complement .



Unbounded from (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free 
     From the complement .




Unbounded from (S3,co-(Cn+4),co-claw,net)-free 
     From the complement .


Unbounded from (S3,co-(Cn+4),co-claw)-free 
     From the complement .





Unbounded from (S3,co-(Cn+4),co-(S3 cup K1),co-claw)-free 
     From the complement .




See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial from nK2-free, fixed n  [1102]
Polynomial from K2 cup claw-free  [1290]
Polynomial from (P5,co-fork)-free  [1161]
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial from 2K2-free  [1160]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

See also : Weighted independent set

Algorithms for Domination

See also : Cliquewidth expression