ISGCI project home  All classes  Smallgraphs

Graphclass: 2-tree

Definition:
See  k-tree, fixed k  .

Related classes:  2-tree cap probe interval   partial 2-tree 

Inclusions

Minimal superclasses:  (0,3)-colorable cap chordal   (5,2)-odd-noncrossing-chordal   (Cn+4,K4)-free   Gallai   HHP-free   K2,3-free   K4-minor-free   cal P3-perfect   absorbantly perfect   alternately orientable   bar visibility   cop-win   disk   dismantlable   genus 1   good   i-triangulated   odd-hole-free cap planar   partial 2-tree   perfect cap planar   quasitriangulated   series-parallel   slightly triangulated   toroidal 
Maximal subclasses:  (0,2)-colorable cap chordal   2-tree cap probe interval   bipartite cap bridged   cycle-free   maximal outerplanar   tree 

Problems summary

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

Algorithms for Recognition

Linear

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Bounded from bounded treewidth 
See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from chordal  [1166]
Linear from bounded treewidth 
Polynomial from (K2,3,P,hole)-free  [1107]
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 [O(VE)] from weakly chordal  [530] [1119]
Polynomial from Meyniel  [169]
Polynomial from clique separable  [1081]
See also : Weighted independent set

Algorithms for Domination

Linear from bounded treewidth 
See also : Cliquewidth expression