ISGCI project home  All classes  Smallgraphs

Graphclass: (3K2,C4 cup P2,C5,C6,K2 cup K3,K3,3,K3,3+e,P2 cup P4,P6,X18,X5,co-(2P3),co-(C6),co-(C7),co-(X84),antenna,domino,fish)-free

Complement classes:  (1,2)-polar   (2K3,2P3,C5,C6,C7,K2,3,K3 cup P3,X84,co-(3K2),co-(C4 cup P2),co-(C6),co-(P2 cup P4),co-(P6),co-(X18),co-(X5),co-antenna,co-domino,co-fish)-free 
See also: X5 P2 cup P4 K3,3 antenna co-(C6) P6 K2 cup K3 co-(2P3) X18 co-(X84) fish 3K2 co-(C7) C6 C5 K3,3+e domino C4 cup P2

Inclusions

Minimal superclasses:  (C6,co-(C6))-free   K2 cup K3-free   P4-bipartite   P6-free   (anti-hole,hole)-free   domino-free   odd-hole-free   weakly chordal 
Maximal subclasses:  (1,1)-colorable   (2K2,C4,C5,S3,net)-free   (2K2,C4,C5)-free   (2K2,K3,3,K3,3+e,P4,co-(2P3))-free   (K3,3,K3,3+e,co-(2P3),co-(Cn+4))-free   (S3,net)-free cap split   chordal cap co-chordal   domishold   split 

Problems summary

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

Algorithms for Recognition


Polynomial
     Finite forbidden subgraph characterization

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from split  [1176]
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

NP-complete from split  [1144] [1145]
See also : Cliquewidth expression