ISGCI project home  All classes  Smallgraphs

Graphclass: (0,2)-colorable cap chordal

Equivalent classes:  bipartite cap bridged   cycle-free   tree 
Complement classes:  co-cycle-free 
Related classes:  (0,2)-colorable   chordal 

Inclusions

Minimal superclasses:  (0,3)-colorable cap chordal   (1,2)-colorable cap chordal   (2,2)-colorable   (2,2)-colorable cap chordal   2-interval   2-split   2-tree   (2K3,Cn+4)-free   3-leaf power   (3K3,Cn+4)-free   (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   (6,2)-chordal cap bipartite   (C4,C6,odd-cycle)-free   (C4,co-claw)-free   C4-free cap C6-free cap bipartite   (C5,P,co-(P),bull,co-fork,gem,house)-free   (Cn+4,K4)-free   (Cn+4,S3,net)-free   (Cn+4,XF12n+3,XF62n+2,co-(X34),co-(X36),co-XF2n+1,co-XF3n)-free   (Cn+4,bull,dart,gem)-free   (Cn+4,diamond)-free   K2,3-free cap hereditary modular   (S3,net)-free cap chordal   X-chordal cap X-conformal cap bipartite   (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   almost tree (1)   (anti-hole,co-sun,hole)-free   bar visibility   basic 4-leaf power   bipartite cap boxicity 2   bipartite cap distance-hereditary   bipartite cap grid intersection   block   cactus   chordal cap comparability   chordal cap diamond-free   comparability cap weakly chordal   directed path   (domino,hole,odd-cycle)-free   domino-free cap modular   hereditary median   k-tree, fixed k   perfect elimination bipartite   ptolemaic cap weakly geodetic   strong tree-cograph   thick tree   tree-perfect   unimodular 
Maximal subclasses:  (T3,X81,cycle)-free   probe interval cap tree 

Problems summary

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

Algorithms for Recognition

Linear from tree 
Polynomial [1249]

Algorithms for Cliquewidth expression

Linear from distance-hereditary  [1177]
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 bounded treewidth 
Bounded from cliquewidth 4 
See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from chordal  [1166]
Linear from bounded treewidth 
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 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 nearly bipartite 
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]
Linear from tree 
     Obvious.

Linear from bounded treewidth 
Polynomial from strongly chordal  [374]
Polynomial from directed path  [524]
Polynomial from almost tree (1)  [524]
Polynomial from cactus  [524]
See also : Cliquewidth expression