ISGCI project home  All classes  Smallgraphs

Graphclass: (2K4,house)-free

Complement classes:  (K4,4,P5)-free 
See also: house 2K4

Inclusions

Minimal superclasses:  house-free 
Maximal subclasses:  (0,2)-colorable   (0,3)-colorable cap chordal   (1,2)-colorable cap chordal   (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   (2K3,Cn+4)-free   (2K3,house)-free   (C4,K4,claw,diamond)-free   (C5,K2 cup K3,K2,3,P,P2 cup P3,P5,co-(P),co-(P2 cup P3),co-fork,fork,house)-free   C5-free cap matrogenic   (Cn+4,K4)-free   (K2 cup K3,house)-free   (K4,P4)-free   XC9-free   (co-(K1,4),house)-free   bipartite   bisplit cap triangle-free   co-interval cap cograph   co-trivially perfect   matrogenic   matroidal   odd-cycle-free   perfect cap triangle-free   probe co-trivially perfect cap probe trivially perfect   probe threshold   pseudo-split   triangle-free 

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 (C4,K4,claw,diamond)-free  [1183]
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