ISGCI project home  All classes  Smallgraphs

Graphclass: proper interval

Definition:
A proper interval graph is an  interval  graph that has an intersection model in which no interval properly contains another.

Equivalent classes:  (Cn+4,S3,claw,net)-free   (Cn+4,XF2n+1,XF3n,claw)-free   (S3,claw,net)-free cap chordal   astral triple-free   chordal cap unit circular arc   claw-free cap interval   indifference   unit interval 
Complement classes:  (S3,co-(Cn+4),co-claw,net)-free   (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free 
Related classes:  interval   proper circular arc   proper tolerance 

Inclusions

Minimal superclasses:  (A,E,S3,X1,domino,hole,house,net,rising sun)-free   AT-free cap chordal   AT-free cap claw-free   (C4,X91,claw)-free   C4-free cap co-comparability   (Cn+4,S3 cup K1,claw,net)-free   (Cn+4,T2,X31,XF2n+1,XF3n)-free   (Cn+4,claw)-free   (Cn+6,X37,claw,co-antenna,net,sun)-free   P4-bipartite   P4-indifference   (W4,claw)-free   boxicity 1   chordal cap claw-free   chordal cap co-comparability   chordal cap proper circular arc   interval   probe unit interval   unit circular arc 
Maximal subclasses:  (2,0)-colorable cap chordal   2-leaf power   (3K1,C4,C5)-free   (C4,odd anti-cycle)-free   P3-free 

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 [248] [301] [295]

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]
Linear from AT-free cap claw-free  [1157]
Polynomial [O(n logn logn)] from trapezoid 
     Timebound valid only when given the model [1120] ; otherwise O(n^2).

Polynomial from K2 cup claw-free  [1290]
Polynomial from (C4,C5,T2)-free  [1108]
Polynomial from fork-free  [1099]
Polynomial [O(n^4)] from AT-free  [160]
Polynomial from (K2,3,P,hole)-free  [1107]
Polynomial [O(n^2)] from circle  [1121]
Polynomial from interval filament  [1159]
Polynomial from claw-free  [783]
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 from claw-free  [947]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
Polynomial from (E,P)-free  [1305]
Polynomial from EPT  [1019]
Polynomial [O(VE)] from (claw,net)-free  [1127] [515]
Polynomial from (P,T2)-free  [1305]
Polynomial from Meyniel  [169]
Polynomial from clique separable  [1081]
Polynomial from (P,star1,2,5)-free  [1349]
Open from (P,star1,2,3)-free  [1351]
Open from (P,star1,2,4)-free  [1351] [1306]
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 [O(VE)] from (claw,net)-free  [1127]
Polynomial from trapezoid  [1155]
Polynomial from probe interval  [1340]
See also : Cliquewidth expression