ISGCI project home  All classes  Smallgraphs

Graphclass: 2-threshold

Definition:
A graph is k-threshold iff its threshold dimension is at most k.

References: [218] [453]
Related classes:  strict 2-threshold   threshold 

Inclusions

Minimal superclasses:  absorbantly perfect   alternately orientable   (anti-hole,hole)-free   perfectly orderable   strict quasi-parity   weakly chordal 
Maximal subclasses:  (2P3,3K2,C4,C5,H,P2 cup P4,P5,S3,X1,X160,co-(X159),co-(X161),co-(X162),co-(X46),co-(X70),net,rising sun)-free   (XC1,XC2,XC3,XC4,XC5,XC6,XC7,XC8)-free   co-bithreshold   co-probe threshold   strict 2-threshold 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unknown to ISGCI details
Cliquewidth: Unknown to ISGCI details
Weighted independent set:Polynomialdetails
Independent set:Polynomialdetails
Domination: Unknown to ISGCI details

Algorithms for Recognition

Polynomial [O(V^3)] [748] [894] [1229]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial from perfect  [476]
Polynomial [O(V^4)] from weakly chordal  [997]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Polynomial [O(VE)] from weakly chordal  [530] [1119]
See also : Weighted independent set

Algorithms for Domination

See also : Cliquewidth expression