ISGCI project home  All classes  Smallgraphs

Graphclass: (E,P)-free

Complement classes:  (co-(E),co-(P))-free 
See also: P E

Inclusions

Minimal superclasses:  BW3-free   E-free   (P,T2)-free   (P,star1,2,3)-free   (P,star1,2,4)-free   (P,star1,2,5)-free   (X79,X80)-free   (co-(X30),co-(XZ1),co-(XZ4),co-longhorn)-free   domino-free 
Maximal subclasses:  (2K2,C4)-free   (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,house)-free   (C5,P,co-fork,fork,gem,house)-free   (K2,3,P,P5)-free   (P,P5,S3,co-(P),co-fork,fork,house,net)-free   (P,P5,co-(P),co-fork,fork,house)-free   (P,P5)-free   (P,co-(P),co-fork,fork)-free   (P,co-butterfly,co-fork,co-gem)-free   (P,co-fork,co-gem)-free   (P,co-gem,house)-free   P4-extendible cap P4-sparse   P4-reducible   P4-sparse   (S3,net)-free cap extended P4-sparse   claw-free   extended P4-reducible   extended P4-sparse   hereditary Welsh-Powell opposition   pseudo-split 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set: Unknown to ISGCI details
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 (2K2,co-(C6),odd anti-cycle)-free 
     From the complement .

Unbounded from (C5,P,P5,co-(P),bull,co-gem,fork)-free  [1185]


Unbounded from co-comparability graphs of posets of interval dimension 2, height 1 
     See  comparability graphs of posets of interval dimension 2, height 1  .



Unbounded from (3K1,co-(H))-free 
     From the complement .

Unbounded from Fn grid  [1176]

Unbounded from unit interval  [1177]



Unbounded from split  [1176]
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 co-bipartite 
     See  bipartite  .

Unbounded from (C4,K4,claw,diamond)-free  [1183]
Unbounded from (3K1,co-cross)-free 
     From the complement .


Unbounded from (2K3,3K1,co-(A),co-(H),co-(X45))-free 
     From the complement .



Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free 
     From the complement .







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


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

Polynomial [1305]
Polynomial from (P,T2)-free  [1305]
Polynomial from (P,star1,2,5)-free  [1349]
Open from (P,star1,2,3)-free  [1351]
Open from (P,star1,2,4)-free  [1351] [1306]
See also : Weighted independent set

Algorithms for Domination

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