ISGCI project home  All classes  Smallgraphs

Graphclass: (W4,claw)-free

References: [666]
Complement classes:  (co-(W4),co-claw)-free 
See also: claw W4

Inclusions

Minimal superclasses:  claw-free 
Maximal subclasses:  (2,0)-colorable cap chordal   (3K1,C4,C5)-free   (C4,X91,claw)-free   (C4,odd anti-cycle)-free   (Cn+4,S3 cup K1,claw,net)-free   (Cn+4,S3,claw,net)-free   (Cn+4,XF2n+1,XF3n,claw)-free   (Cn+4,claw,net)-free   (Cn+4,claw)-free   (S3,claw,net)-free cap chordal   (W4,claw,gem)-free   astral triple-free   chordal cap (claw,net)-free   chordal cap claw-free   chordal cap proper circular arc   chordal cap unit circular arc   claw-free cap interval   domino   indifference   line graphs of multigraphs without triangles   proper interval   unit interval 

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 Fn grid  [1176]
Unbounded from unit interval  [1177]
Unbounded from (C4,K4,claw,diamond)-free  [1183]
See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial from K2 cup claw-free  [1290]
Polynomial from fork-free  [1099]
Polynomial from claw-free  [783]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Polynomial from claw-free  [947]
Polynomial from (E,P)-free  [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

See also : Cliquewidth expression