ISGCI project home  All classes  Smallgraphs

Graphclass: 3-leaf power

Definition:
A connected graph is a 3-leaf power iff it results from at tree by replacing every vertex by a clique of arbitrary size.

References: [1311] [1312]
Equivalent classes:  (Cn+4,bull,dart,gem)-free 
Complement classes:  (co-(Cn+4),bull,co-dart,co-gem)-free 
Related classes:  4-leaf power   block   cactus   k-leaf power, fixed k 

Inclusions

Minimal superclasses:  3-Helly   4-leaf power   (5,2)-crossing-chordal   (Cn+4,S3,net)-free   (Cn+4,XF12n+3,XF62n+2,co-(X34),co-(X36),co-XF2n+1,co-XF3n)-free   (Cn+4,gem)-free   HHDG-free   HHDS-free   Helly chordal   K2,3-free   (S3,net)-free cap chordal   (W4,gem)-free   (XF12n+3,XF52n+3,XF62n+2,co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X35),co-(X36),anti-hole,co-XF2n+1,co-XF3n,co-XF4n,hole)-free   tauk-perfect for all k >= 2   (anti-hole,co-sun,hole)-free   brittle   (bull,house,odd-hole)-free   (bull,house)-free   chordal cap clique-Helly   chordal cap comparability   chordal cap distance-hereditary   chordal cap gem-free   comparability cap weakly chordal   distance-hereditary   (domino,gem,house)-free cap pseudo-modular   gem-free   hereditary homogeneously orderable   (house,hole,domino,sun)-free   house-free   pseudo-modular   ptolemaic 
Maximal subclasses:  (0,2)-colorable cap chordal   (C4,P4,dart)-free   (T3,X81,cycle)-free   bipartite cap bridged   cycle-free   probe interval cap tree   superfragile   tree 

Problems summary

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

Algorithms for Recognition

Linear [1247] [1311]

Algorithms for Cliquewidth expression

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

Algorithms for Cliquewidth

Bounded from cliquewidth 4 
See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from chordal  [1166]
Linear from distance-hereditary 
     Hammer/Maffray's [511] algorithm contained an error that was corrected by Nicolai. [809]

Polynomial [O(V^5E^3)] from Berge cap bull-free  [1278]
Polynomial from parity  [170]
Polynomial from (K2,3,P,hole)-free  [1107]
Polynomial [O(n^2)] from circle  [1121]
Polynomial from interval filament  [1159]
Polynomial from perfect  [476]
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 chordal  [425] [931]
Polynomial from Gallai  [1081]
Polynomial from comparability  [453]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
Polynomial from EPT  [1019]
Polynomial from Meyniel  [169]
Polynomial from clique separable  [1081]
See also : Weighted independent set

Algorithms for Domination

Linear from distance-hereditary  [1153]
Linear from dually chordal  [143] [332]
Polynomial from strongly chordal  [374]
Polynomial from directed path  [524]
See also : Cliquewidth expression