ISGCI project home  All classes  Smallgraphs

Graphclass: co-comparability cup comparability

Complement classes: self-complementary
Related classes:  co-comparability   comparability 

Inclusions

Minimal superclasses:  (S3,S4,net)-free   (S3,net)-free cap sun-free   quasi-parity 
Maximal subclasses:  (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   PI   (XF12n+3,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X35),co-(X36),co-XF2n+1,co-XF3n,co-XF4n,odd-hole)-free   bounded multitolerance   co-comparability   co-comparability cap tolerance   co-comparability graphs of posets of interval dimension 2   co-interval cup interval   comparability   containment graphs   probe unit interval   proper tolerance   trapezoid 

Problems summary

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

Algorithms for Recognition

Polynomial
     From the constituent classes.

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from bipartite permutation  [1182]
Unbounded from (2K2,co-(C6),odd anti-cycle)-free 
     From the complement .



Unbounded from co-comparability graphs of posets of interval dimension 2, height 1 
     See  comparability graphs of posets of interval dimension 2, height 1  .


Unbounded from permutation  [1177]
Unbounded from (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free 
     From the complement .



Unbounded from unit interval  [1177]


Unbounded from (S3,co-(Cn+4),co-claw,net)-free 
     From the complement .






Unbounded from C4-free cap C6-free cap bipartite  [1183]



Unbounded from (P5,S3,co-(A),co-(E),co-(X1),anti-hole,co-domino,co-rising sun,net)-free 
     From the complement .



Unbounded from co-bipartite 
     See  bipartite  .

Unbounded from grid  [1177]

Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free 
     From the complement .







Unbounded from co-interval 
     See  interval  .


See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial from perfect  [476]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

See also : Weighted independent set

Algorithms for Domination

NP-complete from chordal bipartite  [1156]
NP-complete from co-trapezoid  [1172]
NP-complete from bipartite  [1142]
NP-complete from partial grid  [1162] [630]
NP-complete from comparability  [1142]
See also : Cliquewidth expression