ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,C5,triangle)-free

Equivalent classes:  (2K2,odd-cycle)-free   2K2-free cap bipartite   bipartite chain   difference 
Complement classes:  (2,0)-colorable cap chordal   (3K1,C4,C5)-free   (C4,odd anti-cycle)-free 
See also: triangle 2K2 C5

Inclusions

Minimal superclasses:  (0,2)-colorable   (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,co-(X91),co-claw)-free   2K2-free cap probe trivially perfect   (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   (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   (5,2)-crossing-chordal   (6,2)-chordal cap bipartite   AT-free cap bipartite   (C5,C6,C7,C8,P8,X19,X20,X21,X22,gem,house)-free   (C5,P5,co-(P2 cup P3))-free   (C5,P5,co-fish,fish,house)-free   (C5,P5,gem)-free   Dilworth 2   (E,odd-cycle)-free   E-free cap bipartite   HHDG-free   HHDS-free   HHDbicycle-free   (P5,co-(P),gem)-free   (P5,bull,house)-free   (P5,bull,odd anti-hole)-free   (P5,co-fork,house)-free   (P5,cricket)-free   (P5,diamond)-free   (P5,triangle)-free   P6-free cap tripartite   (P7,odd-cycle,star1,2,3,sunlet4)-free   (S3,co-(Cn+4),co-(S3 cup K1),co-claw)-free   (S3,co-(Cn+4),co-claw,net)-free   (S3,co-(Cn+4),co-claw)-free   (T2,X2,X3,hole,triangle)-free   (co-(Cn+4),bull,house)-free   (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free   (co-(Cn+4),co-claw)-free   (co-(W4),co-claw)-free   bi-cograph   bipartite   bipartite cap boxicity 2   bipartite cap distance-hereditary   bipartite cap grid intersection   bipartite permutation   bipartite tolerance   bisplit cap triangle-free   distance-hereditary   (domino,gem,house)-free cap pseudo-modular   (domino,hole,odd-cycle)-free   domino-free cap modular   hereditary Matula perfect   hereditary N*-perfect   hereditary homogeneously orderable   (house,hole,domino,sun)-free   maxibrittle   odd-cycle-free   perfect cap triangle-free   probe co-trivially perfect cap probe trivially perfect   probe threshold   semi-P4-sparse   threshold signed 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression:Lineardetails
Cliquewidth:Boundeddetails
Weighted independent set:Lineardetails
Independent set:Lineardetails
Domination:Lineardetails

Algorithms for Recognition

Polynomial from 2K2-free cap bipartite 
     From the constituent classes.



Polynomial
     Finite forbidden subgraph characterization

Algorithms for Cliquewidth expression

Linear from (P5,bull,house)-free  [1187] [1185]
Linear from semi-P4-sparse  [1186]
Linear from distance-hereditary  [1177]
Linear from (P5,diamond)-free  [1190]
Linear from (P7,odd-cycle,star1,2,3)-free  [1181]
Polynomial [O(n^2+nm)] from (odd-cycle,star1,2,3)-free  [1140]
Polynomial [O(n^2+nm)] from (odd-cycle,star1,2,3,sunlet4)-free  [1139]
Polynomial [O(V^2E)] from cliquewidth 3  [1178]
See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Bounded from difference  [1192]

Bounded from cliquewidth 4 
Bounded from (P5,gem)-free  [1189] [1171] [1185]


Bounded from (P5,bull,co-fork)-free 
     From the complement .

See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from permutation  [1164]
Linear from (P5,gem)-free  [1170]
Linear from distance-hereditary 
     Hammer/Maffray's [511] algorithm contained an error that was corrected by Nicolai. [809]

Polynomial from nK2-free, fixed n  [1102]
Polynomial [O(V^5E^3)] from Berge cap bull-free  [1278]
Polynomial from (P5,cricket)-free  [1110]
Polynomial from semi-P4-sparse  [402]
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 from parity  [170]
Polynomial [O(n^4)] from AT-free  [160]
Polynomial from (P5,co-fork)-free  [1161]
Polynomial from bipartite 
     Variant of matching.

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 nearly bipartite 
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 Gallai  [1081]
Polynomial from (C5,P5,co-(P2 cup P3))-free  [1118]
Polynomial from co-hereditary clique-Helly  [1298]
Polynomial from comparability  [453]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
Polynomial from Meyniel  [169]
Polynomial from clique separable  [1081]
Polynomial from (P5,co-(P2 cup P3))-free  [1350]
Open from (E,odd-cycle)-free  [1351]
See also : Weighted independent set

Algorithms for Domination

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

Polynomial from (K4,P5)-free  [1257]
Polynomial from k-polygon  [352]
Polynomial from co-comparability  [1150] [1151]
Polynomial from convex  [1167]
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 (P5,triangle)-free  [1257]
Polynomial from probe interval  [1340]
See also : Cliquewidth expression