ISGCI project home  All classes  Smallgraphs

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

Equivalent classes:  co-probe threshold 
Complement classes:  (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-free cap probe trivially perfect   probe co-trivially perfect cap probe trivially perfect   probe threshold 
See also: P2 cup P4 X1 2P3 P5 net co-(X162) H X160 co-(X46) co-(X159) S3 co-(X70) co-(X161) 3K2 rising sun C5 C4

Inclusions

Minimal superclasses:  (2,2)-colorable cap chordal   2-threshold   (2P3,3K2,C4 cup P2,C6,K2,3,P6,X130,X132,X134,X152,X153,X154,X155,X156,X157,X158,X18,X84,co-(X11),co-(X127),co-(X128),co-(X129),co-(X131),co-(X133),co-(X135),co-(X136),co-(X137),co-(X138),co-(X139),co-(X140),co-(X141),co-(X142),co-(X143),co-(X144),co-(X145),co-(X146),co-(X147),co-(X148),co-(X149),co-(X150),co-(X151),co-(X30),co-(X35),co-(X46),co-XF12n+3,co-XF62n+3,co-antenna,co-eiffeltower,co-longhorn,domino,fish,odd anti-hole)-free   (2P4,A,C5,C6,C7,E,K3,3-e,P7,R,X1,X103,X5,X58,X84,X98,co-(C6),co-(P6),co-(X5),co-(sunlet4),co-antenna,co-domino,co-rising sun,domino,parachute,parapluie,rising sun,twin-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   (3K3,Cn+4)-free   (A,E,S3,X1,domino,hole,house,net,rising sun)-free   (A,H,K3,3,X45,X46,X47,X48,X49,X50,X51,X52,X53,X54,X55,X56,X57,co-(X42))-free   (A,P6,clique wheel,domino,hole,house)-free   AT-free cap chordal   (C4,C5,T2)-free   (C4,C5)-free   (C4,P5)-free   C4-free cap co-comparability   (C5,P,P5,house)-free   (C5,P5,co-(P2 cup P3))-free   (Cn+4,H)-free   (Cn+4,T2,X31,XF2n+1,XF3n)-free   (Cn+4,T2,net)-free   (Cn+4,X59,longhorn)-free   (Cn+4,XF12n+3,XF62n+2,co-(X34),co-(X36),co-XF2n+1,co-XF3n)-free   Cn+4-free   Dilworth 2   HHDS-free   HHDbicycle-free   HHP-free   (K2,3,P,P5)-free   (K2,3,P5)-free   P4-indifference   (S3,S4,net)-free   (S3,net)-free   (S3,net)-free cap sun-free   bipolarizable   boxicity 1   chordal   chordal cap co-comparability   chordal cap comparability   chordal cap diametral path   chordal cap domination perfect   chordal cap irredundance perfect   circular arc cap comparability   co-bounded tolerance   co-probe cograph   domination perfect   hereditary Matula perfect   hereditary Welsh-Powell opposition   hereditary homogeneously orderable   (house,hole,domino,sun)-free   interval   threshold signed 
Maximal subclasses:  (2,0)-colorable cap chordal   (2K2,C4,C5,H,S3,X160,co-(X159),net,rising sun)-free   (2K2,C4,P4)-free   (3K1,C4,C5)-free   (C4,odd anti-cycle)-free   Dilworth 1   co-interval cap cograph cap interval   co-trivially perfect cap trivially perfect   cograph cap split   comparability graphs of threshold orders   threshold 

Problems summary

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

Algorithms for Recognition


Polynomial
     Finite forbidden subgraph characterization

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth


Bounded from co-probe cograph 
     From the complement  probe cograph  .


Bounded
     From the complement .



Bounded from co-probe threshold 
     From the complement  probe threshold  .

See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from permutation  [1164]
Linear from chordal  [1166]
Polynomial from (K2,3,P5)-free  [1110]
Polynomial from (P,P5)-free  [1353]
Polynomial [O(n logn logn)] from trapezoid 
     Timebound valid only when given the model [1120] ; otherwise O(n^2).

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

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^4)] from AT-free  [160]
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 [O(n^2)] from circle  [1121]
Polynomial from interval filament  [1159]
Polynomial [O(n^{6p+2})] from (p,q<=2)-colorable  [1116]
Polynomial [O(ln)] from circular arc 
     Where l is the minimum number of arcs passing through a given point on the circle. [995]

Polynomial from perfect  [476]
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 [O(n)] from circular arc  [1105] [1106] [1158]
Linear from co-Matula perfect  [221]
Linear from co-Welsh-Powell perfect  [221]
Linear from co-comparability  [1100]
Linear from chordal  [425] [931]
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 EPT  [1019]
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]
Linear from circular arc  [1143] [1158]
Linear [O(V)] from permutation  [1342] [1147] [1148] [1149] [1165]
Linear from interval  [1143]
Polynomial from strongly chordal  [374]
Polynomial from co-interval cup interval 
     From  interval  and  co-interval  .

Polynomial from directed path  [524]
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