ISGCI project home  All classes  Smallgraphs

Graphclass: (2K3 + e,co-(X99),house)-free

Complement classes:  (K3,3-e,P5,X99)-free 
See also: co-(X99) 2K3 + e house

Inclusions

Minimal superclasses:  (2K3 + e,house)-free 
Maximal subclasses:  (0,2)-colorable   (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-free cap probe trivially perfect   (5,1)   (C5,P,P5,S3,co-(P),co-fork,fork,house,net)-free   (C5,P,P5,co-(P),co-fork,fork,house)-free   (C5,P,P5,co-(P),house)-free   (C5,P5,co-(P),house)-free   (K2 cup K3,house)-free   (P,P5,S3,co-(P),co-fork,fork,house,net)-free   (P,P5,co-(P),co-fork,fork,house)-free   P4-extendible cap P4-sparse   P4-reducible   P4-sparse   (S3,net)-free cap extended P4-sparse   (co-(P),fork,house)-free   (co-(P),house)-free   bipartite   bisplit cap triangle-free   extended P4-reducible   extended P4-sparse   odd-cycle-free   paw-free   perfect cap triangle-free   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:NP-completedetails
Independent set:NP-completedetails
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 bipartite permutation  [1182]
Unbounded from Hn,q grid  [1176]
Unbounded from split  [1176]
Unbounded from C4-free cap C6-free cap bipartite  [1183]
Unbounded from grid  [1177]
Unbounded from (C5,P,P5,co-(P),house)-free  [1185]
See also : Cliquewidth expression

Algorithms for Weighted independent set

See also : Cliquewidth expression : Independent set

Algorithms for Independent set

NP-complete from 2-subdivision cap planar 
      2-subdivision cap planar  are precisely the  2-subdivision  graphs of  planar  graphs.

NP-complete from 2-subdivision 
     From Poljak's [1111] construction (which is a 2-subdivision). See also [453]

NP-complete from (C4,C5,C6,C7,C8,H,X85,triangle)-free cap K1,4-free 
     Contains the  2-subdivision  of graphs of max. degree 3. See also  planar of degree 3  .

See also : Weighted independent set

Algorithms for Domination

NP-complete from chordal bipartite  [1156]
NP-complete from bipartite  [1142]
NP-complete from partial grid  [1162] [630]
NP-complete from domination perfect cap triangle-free  [1096]
NP-complete from split  [1144] [1145]
See also : Cliquewidth expression