ISGCI project home  All classes  Smallgraphs

Graphclass: (2P4,A,C5,C6,C7,E,K3,3-e,P7,R,X1,X103,X5,X58,X84,X98,co-(C6),co-(P6),co-(X5),co-(sunlet4),co-antenna,co-domino,co-rising sun,domino,parachute,parapluie,rising sun,twin-house)-free

Complement classes:  (2K3 + e,C5,C6,P6,X5,co-(2P4),co-(A),co-(C6),co-(C7),co-(E),co-(P7),co-(R),co-(X1),co-(X103),co-(X5),co-(X58),co-(X84),co-(X98),antenna,co-domino,co-rising sun,co-twin-house,domino,parachute,parapluie,rising sun,sunlet4)-free 
See also: X5 X84 co-domino X1 co-(C6) P7 2P4 R co-(X5) K3,3-e X98 E A X58 twin-house parapluie co-antenna X103 co-rising sun co-(P6) co-(sunlet4) rising sun C7 C6 C5 domino parachute

Inclusions

Minimal superclasses:  (C6,co-(C6))-free   E-free   P7-free   (co-(P6),co-(X30),co-(X8))-free   (co-(X30),co-(XZ1),co-(XZ4),co-longhorn)-free   (anti-hole,hole)-free   domino-free   odd-hole-free   weakly chordal 
Maximal subclasses:  (2,0)-colorable cap chordal   (2K2,C4,C5,S3,co-rising sun,net,rising sun)-free   (2K2,P4)-free   (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   (3K1,C4,C5)-free   (C4,P4)-free   (C4,odd anti-cycle)-free   P4-free   chordal cap co-chordal cap co-comparability cap comparability   chordal cap cograph   cliquewidth 2   co-interval cap cograph   co-interval cap interval   co-probe cograph   co-probe threshold   co-trivially perfect   cograph   cograph cap interval   comparability graphs of arborescence orders   comparability graphs of series-parallel posets   intersection graph of nested intervals   permutation cap split   quasi-threshold   split cap threshold signed   trivially perfect 

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
     Finite forbidden subgraph characterization

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