ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,P4,co-dart)-free

Complement classes:  (C4,P4,dart)-free   superfragile 
See also: P4 co-dart 2K2

Inclusions

Minimal superclasses:  (2K2,P4)-free   (co-(Cn+4),bull,co-dart,co-gem)-free   co-interval cap cograph   co-trivially perfect 
Maximal subclasses:  co-(P3)-free 

Problems summary

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

Algorithms for Recognition

Polynomial
     Finite forbidden subgraph characterization


Algorithms for Cliquewidth expression

Linear from cliquewidth 2 
Linear from (bull,fork,gem)-free  [1185]
Linear from (P5,bull,house)-free  [1187] [1185]
Linear from (5,1)  [1175]
Linear from (q,q-4), fixed q  [1175]
Linear from (co-(P),fork,gem)-free  [1184] [1185]
Linear from (bull,co-fork,fork)-free  [1124] [1185]
Linear from (P,co-(P),co-fork,fork)-free  [1185]
Linear from partner-limited  [1179]
Linear from semi-P4-sparse  [1186]
Linear from (q, q-3), fixed q>= 7  [1176]
Linear from (bull,fork,house)-free  [1124] [1185]
Linear from (7,3)  [1175]
Linear from P4-tidy  [1175]
Linear from distance-hereditary  [1177]
Linear from (P5,fork,house)-free  [1185] [402]
Linear from (6,2)  [1175]
Linear from (co-(P),fork,house)-free  [1185] [1186]
Linear from (9,6)  [488]
Polynomial from tree-cograph 
     From the decomposition tree.

Polynomial [O(V^2E)] from cliquewidth 3  [1178]
See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth


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






Bounded from (P,co-fork,co-gem)-free 
     From the complement .



Bounded from cliquewidth 4 
Bounded from (co-gem,gem)-free  [1188] [1185]
Bounded from (P,co-gem,house)-free 
     From the complement .


Bounded from (P5,anti-hole,co-domino,co-gem)-free 
     From the complement .




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


Bounded from (co-gem,house)-free 
     From the complement .


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



Bounded from (co-(Cn+4),bull,co-dart,co-gem)-free 
     From the complement .

Bounded from (C5,co-gem,house)-free 
     From the complement .

Bounded from (3K2,co-(P),co-gem,house)-free 
     From the complement .






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


Bounded from (co-(Cn+4),co-gem)-free 
     From the complement .










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 [O(VE)] from (co-(P),fork)-free  [1125]
Polynomial [O(VE)] from (P5,fork)-free  [1125]
Polynomial from nK2-free, fixed n  [1102]
Polynomial [O(V^5E^3)] from Berge cap bull-free  [1278]
Polynomial from semi-P4-sparse  [402]
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 from K2 cup claw-free  [1290]
Polynomial [O(VE)] from co-gem-free 
     Because for all v: G[\co{N}(v)] is P_4-free

Polynomial from (P5,house)-free  [1109]
Polynomial from fork-free  [1099]
Polynomial from parity  [170]
Polynomial [O(n^4)] from AT-free  [160]
Polynomial from (P5,co-fork)-free  [1161]
Polynomial [O(n^2)] from circle  [1121]
Polynomial from (co-(P),butterfly,fork,gem)-free  [1104]
Polynomial from interval filament  [1159]
Polynomial from perfect  [476]
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial [O(VE)] from (bull,fork)-free  [1124] [307]
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 partner-limited  [1180]
Linear from co-chordal  [558]
     See also [425] .

Linear from P4-tidy  [440]
Linear from co-Matula perfect  [221]
Linear from co-Welsh-Powell perfect  [221]
Linear from co-comparability  [1100]
Linear from extended P4-laden  [438]
Polynomial from co-biclique separable  [1304]
Polynomial from co-hereditary clique-Helly  [1298]
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 [O(V^8)] from (P,P7)-free  [1351]
Polynomial from (P,T2)-free  [1305]
Polynomial from Meyniel  [169]
Polynomial [O(nm)] from (K3,3-e,P5,X98)-free  [1117]
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 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 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 cograph  [524]
Polynomial from trapezoid  [1155]
See also : Cliquewidth expression