ISGCI project home  All classes  Smallgraphs

Graphclass: 2-leaf power

Equivalent classes:  P3-free 
Complement classes:  co-(P3)-free 
Related classes:  k-leaf power, fixed k 

Inclusions

Minimal superclasses:  (4-fan,Cn+4,K5 - e,S3,X100,X101,X102,co-(H),co-(K3 cup 2K1))-free   (4-fan,Cn+4,K5 - e,S3,co-(H),co-(K3 cup 2K1))-free   (5,2)-crossing-chordal   AC   AT-free cap claw-free   (C4,C5,C6,C7,C8,claw,diamond)-free   (C4,P4,dart)-free   (C4,X91,claw)-free   (C5,P,P5,S3,co-(P),co-fork,fork,house,net)-free   (C5,P2 cup P3,house)-free   (Cn+4,P5,claw,gem)-free   (Cn+4,S3 cup K1,claw,net)-free   (Cn+4,S3,claw,net)-free   (Cn+4,XF2n+1,XF3n,claw)-free   (Cn+4,claw,gem)-free   (Cn+4,claw,net)-free   (Cn+4,diamond)-free   (Cn+6,X37,claw,co-antenna,net,sun)-free   HHDG-free   HHP-free   Hamiltonian hereditary   Helly   (K1,4,P,P5,fork)-free   (K1,4,P5)-free   (K2,3,X37,X38,diamond,domino,house,twin-C5)-free   (K3 cup P3,co-(C6),co-(P),co-(P7),co-(X37),co-(X41))-free   (K5 - e,W5,co-(A),co-(C4 cup 2K1),co-(P2 cup P3),co-(R),claw,co-twin-C5,co-twin-house)-free   (P2 cup P3,house)-free   P4-extendible cap P4-sparse   P4-free   P4-reducible   (P5,claw)-free   (P5,cricket)-free   (P5,diamond)-free   (S3,claw,net)-free   (S3,claw,net)-free cap chordal   (W4,W5,butterfly)-free   (W4,claw,gem)-free   (co-(P),butterfly,fork,gem)-free   (anti-hole,hole)-free   astral triple-free   basic 4-leaf power   block   chordal cap (claw,net)-free   chordal cap diamond-free   chordal cap domino   chordal cap proper circular arc   chordal cap unit circular arc   circle-polygon   (claw,diamond,odd-hole)-free   (claw,net)-free   (claw,paw)-free   claw-free   claw-free cap interval   clique-Helly   clique-Helly cap dismantlable   cliquewidth 2   (co-cricket,house)-free   (co-paw,odd anti-hole)-free   (co-paw,paw)-free   cograph   comparability graphs of series-parallel posets   directed path   disk-Helly   distance-hereditary   domino   (domino,gem,house)-free cap pseudo-modular   gridline   homogeneously orderable   indifference   k-leaf power, fixed k   line   line graphs of acyclic multigraphs   line graphs of bipartite graphs   line graphs of multigraphs without triangles   (odd-hole,paw)-free   paw-free   paw-free cap perfect   proper interval   ptolemaic cap weakly geodetic   spider graph   superfragile   unit interval   weakly chordal 

Problems summary

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

Algorithms for Recognition

Linear [1247]
Polynomial from P3-free 
     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 (co-paw,paw)-free  [1126]
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 (P5,diamond)-free  [1190]
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 (P,co-butterfly,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 (claw,paw)-free  [1183]


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 (C5,co-gem,house)-free 
     From the complement .






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 P3-free 
     trivial

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

Linear from AT-free cap claw-free  [1157]
Polynomial [O(VE)] from (co-(P),fork)-free  [1125]
Polynomial [O(VE)] from (P5,fork)-free  [1125]
Polynomial [O(n^5)] from (K1,4,P5)-free  [1110]
Polynomial from (K2,3,P5)-free  [1110]
Polynomial [O(V^5E^3)] from Berge cap bull-free  [1278]
Polynomial from (P5,cricket)-free  [1110]
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 [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 [O(VE)] from co-gem-free 
     Because for all v: G[\co{N}(v)] is P_4-free

Polynomial from (C4,C5,T2)-free  [1108]
Polynomial from (P5,house)-free  [1109]
Polynomial from fork-free  [1099]
Polynomial from parity  [170]
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 from (P5,co-fork)-free  [1161]
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 (co-(P),butterfly,fork,gem)-free  [1104]
Polynomial from interval filament  [1159]
Polynomial from (K1,4,P,P5,fork)-free  [1103]
Polynomial [O(n^4)] from (P5,claw)-free  [1110]
Polynomial from claw-free  [783]
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 (P5,X82,X83)-free  [1246]
Polynomial [O(VE)] from (bull,fork)-free  [1124] [307]
Polynomial from (P,P5,co-(3K2),gem)-free  [1114]
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 partner-limited  [1180]
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 chordal  [425] [931]
Linear from extended P4-laden  [438]
Polynomial from Gallai  [1081]
Polynomial from gridline  [871]
Polynomial from (C5,P5,co-(P2 cup P3))-free  [1118]
Polynomial from claw-free  [947]
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 [O(VE)] from (claw,net)-free  [1127] [515]
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 distance-hereditary  [1153]
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 cograph  [524]
Polynomial [O(VE)] from (claw,net)-free  [1127]
Polynomial from trapezoid  [1155]
Polynomial from probe interval  [1340]
See also : Cliquewidth expression