ISGCI project home  All classes  Smallgraphs

Graphclass: bounded tolerance

Definition:
A bounded tolerance graph is a  tolerance  graph in which the tolerances are bounded by the length of the corresponding intervals.

References: [461] [462]
Equivalent classes:  intersection graphs of parallelograms (squares) 
Complement classes:  co-bounded tolerance 
Related classes:  bounded multitolerance   interval   permutation   tolerance 

Inclusions

Minimal superclasses:  alternately orientable   bounded multitolerance   co-comparability cap tolerance   co-comparability graphs of posets of interval dimension 2   diametral path   trapezoid   weak dominating pair 
Maximal subclasses:  AT-free cap chordal   C4-free cap co-comparability   (Cn+4,T2,X31,XF2n+1,XF3n)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd anti-hole)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd-hole)-free   (co-(2C4),co-(3K2),co-(C6),co-(E),co-(P2 cup P4),co-(P6),co-(X25),co-(X26),co-(X27),co-(X28),co-(X29),odd anti-cycle)-free   boxicity 1   chordal cap co-comparability   circle graph with equator   co-comparability cap comparability   co-permutation   comparability graphs of dimension 2 posets   containment graph of intervals   interval   permutation   probe unit interval   proper tolerance 

Problems summary

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

Algorithms for Recognition

Open

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from bipartite permutation  [1182]

Unbounded from permutation  [1177]

Unbounded from unit interval  [1177]



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



See also : Cliquewidth expression

Algorithms for Weighted independent set

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

Polynomial [O(n^4)] from AT-free  [160]
Polynomial from interval filament  [1159]
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 from co-comparability  [1100]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
See also : Weighted independent set

Algorithms for Domination

Polynomial from co-comparability  [1150] [1151]
Polynomial from AT-free  [1152]
Polynomial from trapezoid  [1155]
See also : Cliquewidth expression