ISGCI project home  All classes  Smallgraphs

Graphclass: claw-free

Related classes:  AT-free cap claw-free   Berge cap claw-free   bipartite cap claw-free   chordal cap claw-free   claw-free cap interval   claw-free cap odd anti-hole-free cap tripartite   claw-free cap odd-hole-free cap tripartite   claw-free cap perfect   claw-free cap upper domination perfect 
See also: claw

Inclusions

Minimal superclasses:  (A,H,K3,3,K3,3-e,X45,XZ5,domino)-free   (A,H,K3,3,X45,X46,X47,X48,X49,X50,X51,X52,X53,X54,X55,X56,X57,co-(X42))-free   BW3-free   (E,P)-free   K1,4-free   K2 cup claw-free   K2,3-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   domination perfect   domino-free   fork-free 
Maximal subclasses:  (2,0)-colorable   (2,0)-colorable cap chordal   2-leaf power   (3K1,C4,C5)-free   AT-free cap claw-free   (C4,odd anti-cycle)-free   (Cn+6,X37,claw,co-antenna,net,sun)-free   Hamiltonian hereditary   (K5 - e,W5,co-(A),co-(C4 cup 2K1),co-(P2 cup P3),co-(R),claw,co-twin-C5,co-twin-house)-free   P3-free   (P5,claw)-free   (W4,claw)-free   (co-(T3),co-(X81),co-cycle)-free   (claw,co-claw)-free   (claw,diamond,odd-hole)-free   (claw,net)-free   (claw,odd anti-hole)-free   (claw,odd anti-hole)-free cap tripartite   (claw,odd-hole)-free   (claw,odd-hole)-free cap tripartite   claw-free cap odd anti-hole-free cap tripartite   claw-free cap odd-hole-free cap tripartite   claw-free cap upper domination perfect   co-bipartite   co-cycle-free   gridline   line   line graphs of bipartite graphs   middle   odd anti-cycle-free 

Problems summary

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

Algorithms for Recognition

Polynomial [O(E^{(a+1)/2})] [673]
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 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 (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]



See also : Cliquewidth expression

Algorithms for Weighted independent set

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

Algorithms for Independent set

Polynomial [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

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