ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,C5,S3,X159,X160,X161,X162,X46,X70,co-(2P3),co-(3K2),co-(H),co-(P2 cup P4),co-(X1),co-rising sun,house,net)-free

References: [1345]
Equivalent classes:  2K2-free cap probe trivially perfect   probe co-trivially perfect cap probe trivially perfect   probe threshold 
Complement classes:  (2P3,3K2,C4,C5,H,P2 cup P4,P5,S3,X1,X160,co-(X159),co-(X161),co-(X162),co-(X46),co-(X70),net,rising sun)-free   co-probe threshold 
See also: X161 co-(H) X159 net co-(P2 cup P4) X160 co-(2P3) co-(X1) X46 co-rising sun house S3 co-(3K2) 2K2 X162 X70 C5

Inclusions

Minimal superclasses:  (2K2,C5,co-(T2))-free   (2K2,C5)-free   (2K2,co-(P6))-free   (2K2,house)-free   2K2-free cap probe cograph   (2K3 + e,C5,C6,P6,X5,co-(2P4),co-(A),co-(C6),co-(C7),co-(E),co-(P7),co-(R),co-(X1),co-(X103),co-(X5),co-(X58),co-(X84),co-(X98),antenna,co-domino,co-rising sun,co-twin-house,domino,parachute,parapluie,rising sun,sunlet4)-free   (2K3 + e,co-(X98),house)-free   (2K3 + e,co-(X99),house)-free   (2K3 + e,house)-free   (2K3,X42,co-(A),co-(H),co-(X45),co-(X46),co-(X47),co-(X48),co-(X49),co-(X50),co-(X51),co-(X52),co-(X53),co-(X54),co-(X55),co-(X56),co-(X57))-free   (2K3,house)-free   (2K4,house)-free   (3K2,C4 cup P2,C5,P2 cup P4,P5,S3,X1,X46,X70,co-(3K2),co-(C4 cup P2),co-(P2 cup P4),co-(X1),co-(X46),co-(X70),co-fish,co-rising sun,fish,house,net,rising sun)-free   (C5,P2 cup P3,house)-free   (C5,P5,co-(P),house)-free   (C5,P5,co-fish,fish,house)-free   Dilworth 2   HHDS-free   HHDbicycle-free   (K2 cup K3,X11,X127,X128,X129,X131,X133,X135,X136,X137,X138,X139,X140,X141,X142,X143,X144,X145,X146,X147,X148,X149,X150,X151,X30,X35,X46,XF12n+3,XF62n+3,co-(2P3),co-(3K2),co-(C4 cup P2),co-(C6),co-(P6),co-(X130),co-(X132),co-(X134),co-(X152),co-(X153),co-(X154),co-(X155),co-(X156),co-(X157),co-(X158),co-(X18),co-(X84),antenna,co-domino,co-fish,eiffeltower,longhorn,odd-hole)-free   (K2 cup K3,co-(P),anti-hole)-free   (K2 cup K3,co-(P),house)-free   (K2 cup K3,house)-free   (K3 cup P3,co-(C6),co-(P),co-(P7),co-(X37),co-(X41))-free   (K3,3,3,co-(Cn+4))-free   (P2 cup P3,house)-free   (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,co-(A),anti-hole,co-domino)-free   (P5,co-(P),anti-hole)-free   (S3,S4,net)-free   (S3,co-(Cn+4),co-(T2))-free   (S3,co-(Cn+4),net)-free   (S3,net)-free   (S3,net)-free cap sun-free   (X34,X36,XF2n+1,XF3n,co-(Cn+4),co-XF12n+3,co-XF62n+2)-free   (co-(A),co-(P6),co-domino)-free   (co-(Cn+4),co-(H))-free   (co-(Cn+4),co-(T2),co-(X31),co-XF2n+1,co-XF3n)-free   (co-(Cn+4),co-(T2),co-XF2n+1)-free   (co-(Cn+4),co-(X59),co-longhorn)-free   (co-(Cn+4),co-sun)-free   (co-(Cn+4),net)-free   (co-(Cn+4),odd co-sun)-free   co-(Cn+4)-free   (co-(E),co-(P))-free   (co-(P),co-(P7))-free   (co-(P),co-(P8))-free   (co-(P),co-(T2))-free   (co-(P),co-(star1,2,3))-free   (co-(P),co-star1,2,4)-free   (co-(P),co-star1,2,5)-free   (co-(P),house)-free   absolutely perfect   co-chordal   co-chordal cap comparability   co-chordal cap superperfect   co-interval   co-strongly chordal   comparability graphs of semiorders   even anti-cycle-free   hereditary Matula perfect   hereditary homogeneously orderable   (house,hole,domino,sun)-free   maxibrittle   probe co-trivially perfect   probe split   probe trivially perfect   threshold signed 
Maximal subclasses:  (2K2,C4,C5,S3,X159,X160,co-(H),co-rising sun,net)-free   (2K2,C4,P4)-free   (2K2,C5,triangle)-free   (2K2,odd-cycle)-free   2K2-free cap bipartite   Dilworth 1   bipartite chain   co-interval cap cograph cap interval   co-trivially perfect cap trivially perfect   cograph cap split   comparability graphs of threshold orders   difference   probe threshold cap split   threshold 

Problems summary

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

Algorithms for Recognition

Linear from probe threshold  [1345]
Polynomial
     Finite forbidden subgraph characterization

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Bounded from cliquewidth 4 
See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from permutation  [1164]
Polynomial from nK2-free, fixed n  [1102]
Polynomial [O(n logn logn)] from trapezoid 
     Timebound valid only when given the model [1120] ; otherwise O(n^2).

Polynomial from K2 cup claw-free  [1290]
Polynomial from (P5,house)-free  [1109]
Polynomial [O(n^4)] from AT-free  [160]
Polynomial [O(n^2)] from circle  [1121]
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 [O(V^4)] from weakly chordal  [997]
Polynomial from subtree overlap  [1123]
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 co-comparability  [1100]
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]
Polynomial from Meyniel  [169]
See also : Weighted independent set

Algorithms for Domination

Linear [O(V)] from permutation  [1342] [1147] [1148] [1149] [1165]
Polynomial from co-interval cup interval 
     From  interval  and  co-interval  .

Polynomial from k-polygon  [352]
Polynomial from co-comparability  [1150] [1151]
Polynomial from AT-free  [1152]
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.

Polynomial from trapezoid  [1155]
Polynomial from probe interval  [1340]
See also : Cliquewidth expression