ISGCI project home  All classes  Smallgraphs

Graphclass: 2K2-free cap probe cograph

References: [1345]
Equivalent classes:  probe co-trivially perfect 
Related classes:  2K2-free   probe cograph 

Inclusions

Minimal superclasses:  (2K2,C5,co-(T2))-free   2K2-free   (C6,C8,T2,X3,co-(BW3),co-(W5),co-(W7),co-(X103),co-(X105),co-(X106),co-(X107),co-(X108),co-(X109),co-(X110),co-(X111),co-(X112),co-(X113),co-(X114),co-(X115),co-(X116),co-(X117),co-(X118),co-(X119),co-(X120),co-(X121),co-(X122),co-(X123),co-(X124),co-(X125),co-(X126),co-(X53),co-(X88),co-X104)-free   (K2 cup K3,co-(P),anti-hole)-free   (K3 cup P3,co-(C6),co-(P),co-(P7),co-(X37),co-(X41))-free   (P5,co-(P),anti-hole)-free   (co-(E),co-(P))-free   probe Meyniel   probe co-comparability   probe cograph   probe comparability   slim 
Maximal subclasses:  (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   co-interval cap cograph   co-trivially perfect   probe co-trivially perfect cap probe trivially perfect   probe threshold 

Problems summary

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

Algorithms for Recognition

Linear from probe co-trivially perfect  [1345]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Bounded from cliquewidth 4 
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

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

Algorithms for Domination

See also : Cliquewidth expression