ISGCI project home  All classes  Smallgraphs

Graphclass: chordal cap co-comparability

Equivalent classes:  AT-free cap chordal   C4-free cap co-comparability   (Cn+4,T2,X31,XF2n+1,XF3n)-free   boxicity 1   interval 
Complement classes:  (co-(Cn+4),co-(T2),co-(X31),co-XF2n+1,co-XF3n)-free   co-chordal cap comparability   co-chordal cap superperfect   co-interval   comparability graphs of semiorders 
Related classes:  chordal   co-comparability 

Inclusions

Minimal superclasses:  2-interval   (C4,C5,T2)-free   (Cn+4,S3,net)-free   (Cn+4,T2,XF2n+1)-free   (Cn+4,T2,net)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,co-XF12n+3,co-XF52n+3,co-XF62n+2,odd anti-hole)-free   HHDA-free   HHDS-free   Helly   Helly circular arc   PI   (S3,net)-free cap chordal   (T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,anti-hole,co-XF12n+3,co-XF52n+3,co-XF62n+2,hole)-free   tauk-perfect for all k >= 2   (anti-hole,co-sun,hole)-free   bounded tolerance   boxicity 2   chordal cap diametral path   chordal cap dominating pair   clique-Helly   clique-Helly cap dismantlable   co-comparability   co-interval cup interval   co-threshold tolerance   directed path   disk-Helly   generalized strongly chordal   hereditary homogeneously orderable   homogeneously orderable   (house,hole,domino,sun)-free   intersection graphs of parallelograms (squares)   maximal clique irreducible   probe interval   strongly orderable   totally unimodular   unimodular   weak bipolarizable 
Maximal subclasses:  (2,0)-colorable cap chordal   (2K2,C4,C5,S3,net,rising sun)-free   (2K2,C4,P4)-free   (2P3,3K2,C4,C5,H,P2 cup P4,P5,S3,X1,X160,co-(X159),co-(X161),co-(X162),co-(X46),co-(X70),net,rising sun)-free   (3K1,C4,C5)-free   (C4,odd anti-cycle)-free   (Cn+4,P5,bull)-free   (Cn+4,S3,claw,net)-free   (Cn+4,XF2n+1,XF3n,claw)-free   Dilworth 1   (P5,bull)-free cap interval   (S3,claw,net)-free cap chordal   (T2,cycle)-free   astral triple-free   caterpillar   chordal cap unit circular arc   claw-free cap interval   co-interval cap cograph cap interval   co-probe threshold   co-trivially perfect cap trivially perfect   cograph cap split   comparability graphs of threshold orders   homogeneously representable   indifference   proper interval   threshold   unit interval 

Problems summary

Recognition:Lineardetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:Lineardetails
Independent set:Lineardetails
Domination:Lineardetails

Algorithms for Recognition

Linear from interval  [127] [687] [595] [499]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from unit interval  [1177]
See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from chordal  [1166]
Polynomial [O(n logn logn)] from trapezoid 
     Timebound valid only when given the model [1120] ; otherwise O(n^2).

Polynomial from (C4,C5,T2)-free  [1108]
Polynomial [O(n^4)] from AT-free  [160]
Polynomial from (K2,3,P,hole)-free  [1107]
Polynomial from interval filament  [1159]
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 [O(V^4)] from weakly chordal  [997]
Polynomial from subtree overlap  [1123]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear [O(n)] from circular arc  [1105] [1106] [1158]
Linear from co-comparability  [1100]
Linear from chordal  [425] [931]
Polynomial from Gallai  [1081]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
Polynomial from EPT  [1019]
Polynomial from (P,T2)-free  [1305]
Polynomial from Meyniel  [169]
Polynomial from clique separable  [1081]
See also : Weighted independent set

Algorithms for Domination

Linear from dually chordal  [143] [332]
Linear from circular arc  [1143] [1158]
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 co-comparability  [1150] [1151]
Polynomial from AT-free  [1152]
Polynomial from trapezoid  [1155]
Polynomial from probe interval  [1340]
See also : Cliquewidth expression