ISGCI project home  All classes  Smallgraphs

Graphclass: comparability graphs of semiorders

Definition:
A partial order < is a semi-order if any of the following equivalent coditions hold:

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

Inclusions

Minimal superclasses:  (BW3,W5,W7,X103,X104,X105,X106,X107,X108,X109,X110,X111,X112,X113,X114,X115,X116,X117,X118,X119,X120,X121,X122,X123,X124,X125,X126,X53,X88,co-(C6),co-(C8),co-(T2),co-(X3))-free   Bouchet   (P5,anti-hole,co-domino,co-sun)-free   (S3,S4,net)-free   (S3,co-(Cn+4),net)-free   (S3,net)-free   (S3,net)-free cap sun-free   (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   (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   (co-(Cn+4),co-(T2),co-XF2n+1)-free   (anti-hole,hole,sun)-free   co-bounded tolerance   co-interval cup interval   comparability   comparability cap weakly chordal   comparability graphs of dimension 3 posets   containment graph of circles   containment graphs   good   quasitriangulated   sun-free   sun-free cap weakly chordal   threshold tolerance 
Maximal subclasses:  (2K2,C4,C5,S3,co-rising sun,net)-free   (2K2,C5,S3,X159,X160,X161,X162,X46,X70,co-(2P3),co-(3K2),co-(H),co-(P2 cup P4),co-(X1),co-rising sun,house,net)-free   (2K2,P4)-free   2K2-free cap probe trivially perfect   (S3,co-(Cn+4),co-claw,net)-free   (co-(Cn+4),bull,house)-free   (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free   (co-(T2),co-cycle)-free   co-bithreshold cap split   co-interval cap cograph   co-trivially perfect   comparability cap split   probe co-trivially perfect cap probe trivially perfect   probe threshold   split cap superperfect 

Problems summary

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

Algorithms for Recognition

Linear from co-interval  [995]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth


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


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






Unbounded from co-interval 
     See  interval  .


See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial from nK2-free, fixed n  [1102]
Polynomial from K2 cup claw-free  [1290]
Polynomial from perfect  [476]
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial from 2K2-free  [1160]
Polynomial [O(V^4)] from weakly chordal  [997]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear from co-chordal  [558]
     See also [425] .

Polynomial from co-biclique separable  [1304]
Polynomial from co-hereditary clique-Helly  [1298]
Polynomial from comparability  [453]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
See also : Weighted independent set

Algorithms for Domination

Polynomial from co-interval cup interval 
     From  interval  and  co-interval  .

Polynomial [O(n^2 log^5 n)] from co-bounded tolerance  [1172]
     Assuming a square embedding of the graph is given; finding this is an open problem.

See also : Cliquewidth expression