ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,C4,C5,S3,co-rising sun,net)-free

Equivalent classes:  co-bithreshold cap split   comparability cap split   split cap superperfect 
Complement classes:  (2K2,C4,C5,S3,net,rising sun)-free 
See also: net co-rising sun S3 2K2 C5 C4

Inclusions

Minimal superclasses:  (2,2)-colorable   2-split   (2K2,C4,C5,S3,net)-free   (2K2,C4,C5,co-sun)-free   (2K2,C4,C5,sun)-free   (A,P6,clique wheel,domino,hole,house)-free   (C5,P5,house)-free   (Cn+4,XF12n+3,XF62n+2,co-(X34),co-(X36),co-XF2n+1,co-XF3n)-free   HHD-free cap co-HHD-free   HHDA-free   HHDS-free   Helly chordal cap clique-chordal   Meyniel cap co-Meyniel   (P5,S3,co-(A),co-(E),co-(X1),anti-hole,co-domino,co-rising sun,net)-free   (P5,co-(A),co-(P6),anti clique wheel,anti-hole,co-domino)-free   (P5,anti-hole,co-domino,co-sun)-free   (S3,co-(3K2),co-(E),co-(P2 cup P4))-free   (S3,net)-free cap split   (co-(Cn+4),co-(T2),co-(X31),co-XF2n+1,co-XF3n)-free   (co-(Cn+4),co-sun)-free   (co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X35),co-(X36),co-(X37),co-(X38),co-(X39),co-(X40),co-(X41),co-XF2n+1,co-XF3n,co-XF4n)-free   (anti-hole,co-sun,hole)-free   bipolarizable   chordal cap comparability   chordal cap dually chordal   circle-polygon   clique separable   co-bithreshold   co-chordal cap comparability   co-chordal cap superperfect   co-interval   co-strongly chordal   co-tolerance   co-trapezoid   comparability graphs of posets of interval dimension 2   comparability graphs of semiorders   doubly chordal   generalized strongly chordal   hereditary clique-Helly   hereditary homogeneously orderable   hereditary maximal clique irreducible   (house,hole,domino,sun)-free   isometric-hereditary pseudo-modular   polar   spider graph   split cap strongly chordal   split-neighbourhood   strongly orderable   weak bipolarizable 
Maximal subclasses:  (2K2,C4,C5,H,S3,X160,co-(X159),net,rising sun)-free   (2K2,C4,C5,S3,X159,X160,co-(H),co-rising sun,net)-free   (2K2,C4,C5,S3,co-rising sun,net,rising sun)-free   (2K2,C4,P4)-free   Dilworth 1   chordal cap co-chordal cap co-comparability cap comparability   co-interval cap cograph cap interval   co-interval cap interval   co-trivially perfect cap trivially perfect   cograph cap split   comparability graphs of threshold orders   permutation cap split   probe threshold cap split   split cap threshold signed   threshold 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unknown to ISGCI details
Cliquewidth: Unknown to ISGCI details
Weighted independent set:Lineardetails
Independent set:Lineardetails
Domination:Lineardetails

Algorithms for Recognition


Polynomial
     Finite forbidden subgraph characterization

Polynomial from comparability cap split 
     From the constituent classes.

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from chordal  [1166]
Linear from (2K2,C4)-free 
Polynomial from nK2-free, fixed n  [1102]
Polynomial from (K2,3,P5)-free  [1110]
Polynomial from (P,P5)-free  [1353]
Polynomial [O(n^4)] from (C4,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from K2 cup claw-free  [1290]
Polynomial from (C4,C5,T2)-free  [1108]
Polynomial from (P5,house)-free  [1109]
Polynomial [O(n^6)] from (K3,3,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial [O(n^8)] from (K4,4,P5)-free 
     Algorithm for (P_5,K_{m,m})-free (fixed m) [1118]

Polynomial from (K2,3,P,hole)-free  [1107]
Polynomial from interval filament  [1159]
Polynomial [O(n^{6p+2})] from (p,q<=2)-colorable  [1116]
Polynomial from perfect  [476]
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial from 2K2-free  [1160]
Polynomial from (K2,3,P,P5)-free  [1107]
Polynomial [O(V^4)] from weakly chordal  [997]
Polynomial from subtree overlap  [1123]
Polynomial from (C4,P6)-free  [1353]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

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

Linear from co-Matula perfect  [221]
Linear from co-Welsh-Powell perfect  [221]
Linear from chordal  [425] [931]
Linear from extended P4-laden  [438]
Polynomial from co-biclique separable  [1304]
Polynomial from Gallai  [1081]
Polynomial from (C5,P5,co-(P2 cup P3))-free  [1118]
Polynomial from co-hereditary clique-Helly  [1298]
Polynomial from (C4,P6)-free  [1351] [1352]
Polynomial from comparability  [453]
Polynomial from (K3,3-e,P5)-free  [1246]
Polynomial [O(VE)] from (P,P5)-free  [1117]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
Polynomial from (E,P)-free  [1305]
Polynomial from (K2,3,P,P5)-free  [1346] [1107]
Polynomial [O(V^8)] from (P,P7)-free  [1351]
Polynomial from (C6,K3,3+e,P,P7,X37,X41)-free  [1346]
Polynomial from (P,T2)-free  [1305]
Polynomial from Meyniel  [169]
Polynomial [O(nm)] from (K3,3-e,P5,X98)-free  [1117]
Polynomial from clique separable  [1081]
Polynomial from (P5,co-(P2 cup P3))-free  [1350]
Polynomial from (P,star1,2,5)-free  [1349]
Polynomial [O(V^{5})] from (K3,3-e,P5,X99)-free  [1307]
Polynomial from (P,P8)-free  [1306]
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

Linear from dually chordal  [143] [332]
Polynomial from strongly chordal  [374]
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