ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,4K1,co-claw,co-diamond)-free

Complement classes:  (C4,K4,claw,diamond)-free 
See also: co-diamond co-claw 2K2 4K1

Inclusions

Minimal superclasses:  (2K2,A,H)-free   (2K2,co-diamond)-free   4K1-free   (A,C4 cup 2K1,P2 cup P3,R,co-(K5 - e),co-(W5),co-claw,twin-C5,twin-house)-free   (K1,4,P5)-free   N*   (P5,co-fork)-free   (P5,cricket)-free   (P5,fork)-free   (co-(K1,4),co-diamond)-free   (co-(P),fork)-free   (co-(W4),co-claw,co-gem)-free   (co-(XC11),co-claw,co-diamond)-free   co-(XC11)-free   (co-claw,co-diamond)-free 

Problems summary

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

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 .

See also : Cliquewidth expression

Algorithms for Weighted independent set

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 (P5,cricket)-free  [1110]
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 from (P5,co-fork)-free  [1161]
Polynomial [O(n^8)] from (K4,4,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from 4K1-free 
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial from 2K2-free  [1160]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Polynomial from co-hereditary clique-Helly  [1298]
See also : Weighted independent set

Algorithms for Domination

See also : Cliquewidth expression