ISGCI project home  All classes  Smallgraphs

Graphclass: (Cn+6,X37,claw,co-antenna,net,sun)-free

References: [1098]
Equivalent classes:  AT-free cap claw-free 
Complement classes:  (S3,co-(Cn+6),co-(X37),antenna,co-claw,co-sun)-free 
See also: Cn+6 net claw co-antenna X37 sun

Inclusions

Minimal superclasses:  AT-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,X40,X41,XF2n+1,XF3n,XF4n)-free   (S3,claw,net)-free   claw-free   diametral path   weak dominating pair 
Maximal subclasses:  (2,0)-colorable   (2,0)-colorable cap chordal   2-leaf power   (2K3 + e,3K1,C5,co-(T2),co-(X18),co-(X94),co-domino)-free   (3K1,C4,C5)-free   (3K1,C5,K3 cup K4,co-(BW3),co-(K3,4-e),co-(T2),co-(X18),co-(X92),co-(X93))-free   (3K1,C5,butterfly,diamond)-free   (3K1,co-(E))-free   (3K1,co-(H))-free   (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free   (3K1,co-cross)-free   (C4,odd anti-cycle)-free   (Cn+4,S3,claw,net)-free   (Cn+4,XF2n+1,XF3n,claw)-free   P3-free   (S3,claw,net)-free cap chordal   (co-(P7),co-(star1,2,3),odd anti-cycle)-free   (co-(T3),co-(X81),co-cycle)-free   (co-(star1,2,3),co-(sunlet4),odd anti-cycle)-free   (anti-hole,co-domino,odd anti-cycle)-free   astral triple-free   chordal cap unit circular arc   claw-free cap interval   co-bipartite   co-cycle-free   indifference   odd anti-cycle-free   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:Polynomialdetails

Algorithms for Recognition

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

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










See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from AT-free cap claw-free  [1157]
Polynomial from K2 cup claw-free  [1290]
Polynomial from fork-free  [1099]
Polynomial [O(n^4)] from AT-free  [160]
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 [O(VE)] from (claw,net)-free  [1127] [515]
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

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