ISGCI project home  All classes  Smallgraphs

Graphclass: co-perfectly orderable

Complement classes:  perfectly orderable 
Related classes:  bipartite cap co-perfectly orderable 

Inclusions

Minimal superclasses:  quasi-parity 
Maximal subclasses:  (6,1)-chordal cap bipartite   (A,P6,clique wheel,domino,hole,house)-free   AT-free cap bipartite   (C5,C6,P6,co-(C6),co-(P6),co-(X17),co-(X18),co-(X5),co-(X98),co-antenna,co-domino)-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   HHG-free   (T2,X2,X3,hole,triangle)-free   X-conformal cap bipartite cap hereditary X-chordal   bipartite cap co-perfectly orderable   bipartite cap weakly chordal   bipartite permutation   bipartite tolerance   bipolarizable   bithreshold   bounded multitolerance   brittle   charming   chordal bipartite   co-Matula perfect   co-P4-brittle   co-Welsh-Powell perfect   co-bithreshold   co-charming   co-comparability   co-comparability graphs of posets of interval dimension 2   hereditary perfect elimination bipartite   (hole,odd-cycle)-free   interval bigraph   probe unit interval   proper tolerance   tolerance   trapezoid 

Problems summary

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

Algorithms for Recognition

NP-complete
     From the complement  perfectly orderable  .

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 co-P4-brittle 
     See  P4-brittle 


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



Unbounded from co-Welsh-Powell perfect 
     See  Welsh-Powell perfect  .



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

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








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 chordal  [1174]

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





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






Unbounded from (co-(Cn+4),co-(H))-free 
     From the complement .


Unbounded from (C5,P,P5,co-(P),house)-free  [1185]

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  [1146]
NP-complete from chordal bipartite  [1156]
NP-complete from undirected path  [1146]
NP-complete from split  [1144] [1145]
See also : Cliquewidth expression