ISGCI project home  All classes  Smallgraphs

Graphclass: (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free

Equivalent classes:  (S3,co-(Cn+4),co-claw,net)-free 
Complement classes:  (Cn+4,S3,claw,net)-free   (Cn+4,XF2n+1,XF3n,claw)-free   (S3,claw,net)-free cap chordal   astral triple-free   chordal cap unit circular arc   claw-free cap interval   indifference   proper interval   unit interval 
See also: co-XF3n co-(Cn+4) co-claw co-XF2n+1

Inclusions

Minimal superclasses:  (2K2,co-(X91),co-claw)-free   (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   Bouchet   P4-bipartite   (P5,S3,co-(A),co-(E),co-(X1),anti-hole,co-domino,co-rising sun,net)-free   (P5,co-fork)-free   (S3,S4,net)-free   (S3,co-(Cn+4),co-(S3 cup K1),co-claw)-free   (S3,co-(Cn+6),co-(X37),antenna,co-claw,co-sun)-free   (S3,co-claw,net)-free   (S3,co-claw)-free   (S3,net)-free   (S3,net)-free cap sun-free   (XF12n+3,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X35),co-(X36),co-XF2n+1,co-XF3n,co-XF4n,odd-hole)-free   (XF12n+3,XF52n+3,XF62n+2,co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X35),co-(X36),anti-hole,co-XF2n+1,co-XF3n,co-XF4n,hole)-free   (co-(Cn+4),co-(T2),co-(X31),co-XF2n+1,co-XF3n)-free   (co-(Cn+4),co-sun)-free   (co-(W4),co-claw)-free   (anti-hole,hole,sun)-free   co-chordal cap comparability   co-chordal cap superperfect   co-interval   co-strongly chordal   co-tolerance   co-trapezoid   comparability   comparability cap weakly chordal   comparability graphs of posets of interval dimension 2   comparability graphs of semiorders   containment graphs   sun-free   sun-free cap weakly chordal 
Maximal subclasses:  (2K2,C5,triangle)-free   (2K2,odd-cycle)-free   2K2-free cap bipartite   co-(P3)-free   bipartite chain   difference 

Problems summary

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

Algorithms for Recognition






Linear from (S3,co-(Cn+4),co-claw,net)-free 
     From the complement .

Linear
     From the complement .




Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth


Unbounded
     From the complement .


Unbounded from (S3,co-(Cn+4),co-claw,net)-free 
     From the complement .







See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial from nK2-free, fixed n  [1102]
Polynomial from K2 cup claw-free  [1290]
Polynomial from (P5,co-fork)-free  [1161]
Polynomial from perfect  [476]
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial from 2K2-free  [1160]
Polynomial [O(V^4)] from weakly chordal  [997]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear from co-chordal  [558]
     See also [425] .

Polynomial from co-biclique separable  [1304]
Polynomial from co-hereditary clique-Helly  [1298]
Polynomial from comparability  [453]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
See also : Weighted independent set

Algorithms for Domination

Polynomial from co-interval cup interval 
     From  interval  and  co-interval  .

Polynomial [O(n^2 log^5 n)] from co-bounded tolerance  [1172]
     Assuming a square embedding of the graph is given; finding this is an open problem.

See also : Cliquewidth expression