ISGCI project home  All classes  Smallgraphs

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

Equivalent classes:  (S3,net)-free cap split 
Complement classes: self-complementary
See also: net S3 2K2 C5 C4

Inclusions

Minimal superclasses:  (1,1)-colorable   (1,2)-colorable cap chordal   (1,2)-polar   (1,2)-polar cap chordal   (2,2)-colorable cap chordal   (2K2,C4,C5)-free   (2K2,C5,co-(T2))-free   (2K2,C5)-free   (2K3,2P3,C5,C6,C7,K2,3,K3 cup P3,X84,co-(3K2),co-(C4 cup P2),co-(C6),co-(P2 cup P4),co-(P6),co-(X18),co-(X5),co-antenna,co-domino,co-fish)-free   (2K3,2P3,Cn+4,K3 cup P3)-free   (2K3,Cn+4)-free   (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   3-Helly   (3K2,C4 cup P2,C5,C6,K2 cup K3,K3,3,K3,3+e,P2 cup P4,P6,X18,X5,co-(2P3),co-(C6),co-(C7),co-(X84),antenna,domino,fish)-free   (3K2,E,P2 cup P4,net)-free   (3K3,Cn+4)-free   (A,C5,P5,co-(A),house,parachute,parapluie)-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   (C4,C5,T2)-free   (C4,C5)-free   C4-free cap induced-hereditary pseudo-modular   (C5,C6,P6,X17,X18,X5,X98,co-(C6),co-(P6),antenna,domino)-free   (C5,C6,P6,co-(C6),co-(P6),co-(X17),co-(X18),co-(X5),co-(X98),co-antenna,co-domino)-free   (C5,P,P5,co-(P),house)-free   (C5,P,P5,house)-free   (C5,P2 cup P3,house)-free   (C5,P5,co-(P),house)-free   (C5,P5,co-(P2 cup P3))-free   (C5,P5)-free   (C5,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   (C6,P6,co-(P6),co-(X10),co-(X11),co-(X12),co-(X13),co-(X14),co-(X15),co-(X5),co-(X6),co-(X7),co-(X8),co-(X9),anti-hole,co-antenna)-free   (Cn+4,S3,net)-free   (Cn+4,S3)-free   (Cn+4,T2,XF2n+1)-free   (Cn+4,T2,net)-free   (Cn+4,X59,longhorn)-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,3,P,hole)-free   (K3,3,3,co-(Cn+4))-free   (K3,3,K3,3+e,co-(2P3),co-(Cn+4))-free   (K3,3,co-(Cn+4))-free   (P5,co-(A),anti-hole,co-domino)-free   (P5,co-(C6))-free cap weakly chordal   (P5,co-(P),anti-hole)-free   (P5,anti-hole,co-bicycle,co-domino)-free   (P5,anti-hole,co-domino)-free   (P5,anti-hole)-free   (S3,co-(3K2),co-(E),co-(P2 cup P4))-free   (S3,co-(Cn+4),co-(T2))-free   (S3,co-(Cn+4),net)-free   (S3,net)-free   (S3,net)-free cap chordal   S3-free cap chordal   (W4,W5,butterfly)-free   (co-(Cn+4),co-(T2),co-XF2n+1)-free   (co-(Cn+4),co-(X59),co-longhorn)-free   (co-(Cn+4),net)-free   (co-(Cn+4),odd co-sun)-free   co-(Cn+4)-free   (co-(W4),co-(W5),co-butterfly)-free   tauk-perfect for all k >= 2   absolutely perfect   chordal cap co-chordal   chordal cap diametral path   chordal cap dominating pair   chordal cap hereditary clique-Helly   chordal cap irredundance perfect   co-HHD-free   co-chordal   co-hereditary clique-Helly   hereditary Helly   hereditary Matula perfect   hereditary V-perfect   hereditary Welsh-Powell opposition   hereditary clique-Helly   hereditary disk-Helly   hereditary maximal clique irreducible   neighbourhood perfect   neighbourhood-Helly   odd co-sun-free   perfect connected-dominant   probe split   pseudo-modular   split   superbrittle 
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)-free   (2K2,C4,C5,S3,net,rising sun)-free   co-bithreshold cap split   comparability cap split   probe threshold cap split   split cap superperfect 

Problems summary

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

Algorithms for Recognition

Polynomial
     Finite forbidden subgraph characterization

Polynomial from (S3,net)-free 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 (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

See also : Cliquewidth expression