ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(X85))-free

Complement classes:  (C4,C5,C6,C7,C8,H,X85,triangle)-free 
See also: co-(H) co-(C6) co-(X85) co-(C8) 2K2 3K1 co-(C7) C5

Inclusions

Minimal superclasses:  (2K2,C5)-free   (2K2,claw)-free   (2K2,co-diamond)-free   (2K3,2K3 + e,co-(A),co-(H),co-(X45),co-(XZ5),co-domino)-free   (2K3,3K1,co-(A),co-(H),co-(X45))-free   (2K3,X42,co-(A),co-(H),co-(X45),co-(X46),co-(X47),co-(X48),co-(X49),co-(X50),co-(X51),co-(X52),co-(X53),co-(X54),co-(X55),co-(X56),co-(X57))-free   (3K1,co-(H))-free   (C5,P,P5,co-(P),bull,co-gem,fork)-free   (C6,co-(C6))-free   (K2 cup K3,P5,co-(X37),co-(X38),co-diamond,co-domino,co-twin-C5)-free   (K2,3,P,hole)-free   (P5,co-(C6))-free   (co-(P),fork)-free   (claw,odd-hole)-free   claw-free cap upper domination perfect   odd-hole-free 
Maximal subclasses:  (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(K1,4),co-(X85))-free 

Problems summary

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

Algorithms for Recognition


Polynomial
     Finite forbidden subgraph characterization

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded
     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 .





See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from AT-free cap claw-free  [1157]
Polynomial [O(VE)] from (co-(P),fork)-free  [1125]
Polynomial [O(VE)] from (P5,fork)-free  [1125]
Polynomial [O(n^5)] from (K1,4,P5)-free  [1110]
Polynomial from nK2-free, fixed n  [1102]
Polynomial from (K2,3,P5)-free  [1110]
Polynomial from (P5,cricket)-free  [1110]
Polynomial from (P,P5)-free  [1353]
Polynomial from K2 cup claw-free  [1290]
Polynomial [O(VE)] from co-gem-free 
     Because for all v: G[\co{N}(v)] is P_4-free

Polynomial from fork-free  [1099]
Polynomial [O(n^6)] from (K3,3,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial [O(n^4)] from AT-free  [160]
Polynomial [O(n^8)] from (K4,4,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from (K2,3,P,hole)-free  [1107]
Polynomial from 4K1-free 
Polynomial from (K1,4,P,P5,fork)-free  [1103]
Polynomial [O(n^4)] from (P5,claw)-free  [1110]
Polynomial from claw-free  [783]
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial [O(VE)] from (bull,fork)-free  [1124] [307]
Polynomial from 2K2-free  [1160]
Polynomial from (K2,3,P,P5)-free  [1107]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Polynomial from claw-free  [947]
Polynomial from co-hereditary clique-Helly  [1298]
Polynomial from (K3,3-e,P5)-free  [1246]
Polynomial [O(VE)] from (P,P5)-free  [1117]
Polynomial from (E,P)-free  [1305]
Polynomial from (K2,3,P,P5)-free  [1346] [1107]
Polynomial [O(V^8)] from (P,P7)-free  [1351]
Polynomial from (C6,K3,3+e,P,P7,X37,X41)-free  [1346]
Polynomial [O(VE)] from (claw,net)-free  [1127] [515]
Polynomial from (P,T2)-free  [1305]
Polynomial [O(nm)] from (K3,3-e,P5,X98)-free  [1117]
Polynomial from (P,star1,2,5)-free  [1349]
Polynomial [O(V^{5})] from (K3,3-e,P5,X99)-free  [1307]
Polynomial from (P,P8)-free  [1306]
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

Polynomial from AT-free  [1152]
Polynomial [O(VE)] from (claw,net)-free  [1127]
See also : Cliquewidth expression