ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,house)-free

Complement classes:  (C4,P5)-free 
See also: house 2K2

Inclusions

Minimal superclasses:  (2K2,co-(P6))-free   (K2 cup K3,co-(P),house)-free   (K2 cup K3,house)-free   (P2 cup P3,house)-free   (P5,house)-free   even anti-cycle-free 
Maximal subclasses:  (2K2,C4)-free   (2K2,C5,S3,X159,X160,X161,X162,X46,X70,co-(2P3),co-(3K2),co-(H),co-(P2 cup P4),co-(X1),co-rising sun,house,net)-free   (2K2,P4)-free   2K2-free cap probe trivially perfect   (co-(Cn+4),bull,house)-free   (co-(Cn+4),co-claw,co-gem,house)-free   co-interval cap cograph   co-trivially perfect   probe co-trivially perfect cap probe trivially perfect   probe threshold   pseudo-split 

Problems summary

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

Algorithms for Recognition


Polynomial
     Finite forbidden subgraph characterization

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

Polynomial from nK2-free, fixed n  [1102]
Polynomial from K2 cup claw-free  [1290]
Polynomial from (P5,house)-free  [1109]
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

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