ISGCI project home  All classes  Smallgraphs

Graphclass: (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

Equivalent classes:  Dilworth 2   threshold signed 
Complement classes: self-complementary
See also: P2 cup P4 X1 P5 net co-(P2 cup P4) co-(X46) co-(X1) X46 co-rising sun house S3 co-(X70) fish co-(C4 cup P2) co-(3K2) 3K2 X70 rising sun C5 co-fish C4 cup P2

Inclusions

Minimal superclasses:  (3K2,E,P2 cup P4,net)-free   (C5,P5,co-fish,fish,house)-free   (C6,C8,T2,X3,co-(BW3),co-(W5),co-(W7),co-(X103),co-(X105),co-(X106),co-(X107),co-(X108),co-(X109),co-(X110),co-(X111),co-(X112),co-(X113),co-(X114),co-(X115),co-(X116),co-(X117),co-(X118),co-(X119),co-(X120),co-(X121),co-(X122),co-(X123),co-(X124),co-(X125),co-(X126),co-(X53),co-(X88),co-X104)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,co-XF12n+3,co-XF52n+3,co-XF62n+2,odd anti-hole)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd anti-hole)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd-hole)-free   Dilworth 3   HHDS-free   (P5,anti-hole,co-domino,co-sun)-free   (S3,co-(3K2),co-(E),co-(P2 cup P4))-free   (T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,anti-hole,co-XF12n+3,co-XF52n+3,co-XF62n+2,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+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   boxicity 2   circle   circle graph with equator   co-Meyniel   co-comparability   co-comparability cap comparability   co-hereditary clique-Helly   co-interval cup interval   co-permutation   co-tolerance   co-trapezoid   comparability cap weakly chordal   comparability graphs of dimension 2 posets   comparability graphs of dimension 4 posets   comparability graphs of posets of interval dimension 2   containment graph of intervals   hereditary clique-Helly   hereditary homogeneously orderable   hereditary maximal clique irreducible   (house,hole,domino,sun)-free   house-free   maxibrittle   permutation 
Maximal subclasses:  (2,0)-colorable cap chordal   (2K2,C4,C5,S3,co-rising sun,net,rising sun)-free   (2K2,C4,P4)-free   (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   (2K2,C5,triangle)-free   (2K2,odd-cycle)-free   2K2-free cap bipartite   2K2-free cap probe trivially perfect   (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   (3K1,C4,C5)-free   (C4,odd anti-cycle)-free   Dilworth 1   bipartite chain   chordal cap co-chordal cap co-comparability cap comparability   co-interval cap cograph cap interval   co-interval cap interval   co-probe threshold   co-trivially perfect cap trivially perfect   cograph cap split   comparability graphs of threshold orders   difference   permutation cap split   probe co-trivially perfect cap probe trivially perfect   probe threshold   split cap threshold signed   threshold 

Problems summary

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

Algorithms for Recognition

Linear from threshold signed  [87]
Polynomial
     Finite forbidden subgraph characterization

Polynomial [O(V^2)] from Dilworth 2  [385] [570]

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 permutation  [1164]
Polynomial [O(n logn logn)] from trapezoid 
     Timebound valid only when given the model [1120] ; otherwise O(n^2).

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 from perfect  [476]
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-Matula perfect  [221]
Linear from co-Welsh-Powell perfect  [221]
Linear from co-comparability  [1100]
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]
See also : Cliquewidth expression