ISGCI project home  All classes  Smallgraphs

Graphclass: (Cn+4,claw)-free

Equivalent classes:  chordal cap claw-free 
Complement classes:  (co-(Cn+4),co-claw)-free 
See also: claw Cn+4

Inclusions

Minimal superclasses:  (5,2)-odd-noncrossing-chordal   (BW3,W5,W7,X103,X104,X105,X106,X107,X108,X109,X110,X111,X112,X113,X114,X115,X116,X117,X118,X119,X120,X121,X122,X123,X124,X125,X126,X53,X88,co-(C6),co-(C8),co-(T2),co-(X3))-free   Berge cap claw-free   Bouchet   (C4,C5,T2)-free   (Cn+4,H)-free   Gallai   HHP-free   (W4,claw)-free   absorbantly perfect   chordal cap domination perfect   circle-polygon   (claw,odd anti-hole,odd-hole)-free   claw-free cap perfect   claw-free cap upper domination perfect   cop-win   dismantlable   (fork,house)-free   good   i-triangulated   perfectly orderable   quasitriangulated   slightly triangulated   spider graph 
Maximal subclasses:  AC   (Cn+4,P5,claw,gem)-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,gem)-free   (Cn+4,claw,net)-free   (S3,claw,net)-free cap chordal   astral triple-free   chordal cap (claw,net)-free   chordal cap domino   chordal cap proper circular arc   chordal cap unit circular arc   claw-free cap interval   indifference   line graphs of acyclic multigraphs   proper interval   unit interval 

Problems summary

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

Algorithms for Recognition



Polynomial from chordal cap claw-free 
     From the constituent classes.


Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from unit interval  [1177]
See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from chordal  [1166]
Polynomial from K2 cup claw-free  [1290]
Polynomial from (C4,C5,T2)-free  [1108]
Polynomial from fork-free  [1099]
Polynomial from (K2,3,P,hole)-free  [1107]
Polynomial from interval filament  [1159]
Polynomial from claw-free  [783]
Polynomial from perfect  [476]
Polynomial [O(V^4)] from weakly chordal  [997]
Polynomial from subtree overlap  [1123]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear from chordal  [425] [931]
Polynomial from Gallai  [1081]
Polynomial from claw-free  [947]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
Polynomial from (E,P)-free  [1305]
Polynomial from (P,T2)-free  [1305]
Polynomial from Meyniel  [169]
Polynomial from clique separable  [1081]
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