ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,A,H)-free

Equivalent classes:  N* 
Complement classes:  (C4,co-(A),co-(H))-free 
See also: H A 2K2

Inclusions

Minimal superclasses:  2K2-free   (A,P6,domino)-free 
Maximal subclasses:  (2K2,4K1,co-claw,co-diamond)-free   (2K2,C4,C5,H,S3,X160,co-(X159),net,rising sun)-free   (2K2,C5,co-(C6),co-(C7),co-(C8),co-claw,co-diamond)-free   (2K2,P4)-free   (2K2,claw)-free   (2K2,co-diamond)-free   (co-(Cn+4),co-diamond)-free   co-interval cap cograph   co-trivially perfect 

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 (2K2,co-(C6),odd anti-cycle)-free 
     From the complement .

Unbounded from (2K2,C5,co-(C6),co-(C7),co-(C8),co-claw,co-diamond)-free 
     From the complement .





Unbounded from (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(X85))-free 
     From the complement .





Unbounded from (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(K1,4),co-(X85))-free 
     From the complement .

Unbounded from (2K2,co-diamond)-free 
     From the complement .










Unbounded from (2K2,claw)-free  [1183]

Unbounded from (2K2,4K1,co-claw,co-diamond)-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,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