ISGCI project home  All classes  Smallgraphs

Graphclass: (2P3,3K2,C4 cup P2,C6,K2,3,P6,X130,X132,X134,X152,X153,X154,X155,X156,X157,X158,X18,X84,co-(X11),co-(X127),co-(X128),co-(X129),co-(X131),co-(X133),co-(X135),co-(X136),co-(X137),co-(X138),co-(X139),co-(X140),co-(X141),co-(X142),co-(X143),co-(X144),co-(X145),co-(X146),co-(X147),co-(X148),co-(X149),co-(X150),co-(X151),co-(X30),co-(X35),co-(X46),co-XF12n+3,co-XF62n+3,co-antenna,co-eiffeltower,co-longhorn,domino,fish,odd anti-hole)-free

Complement classes:  (K2 cup K3,X11,X127,X128,X129,X131,X133,X135,X136,X137,X138,X139,X140,X141,X142,X143,X144,X145,X146,X147,X148,X149,X150,X151,X30,X35,X46,XF12n+3,XF62n+3,co-(2P3),co-(3K2),co-(C4 cup P2),co-(C6),co-(P6),co-(X130),co-(X132),co-(X134),co-(X152),co-(X153),co-(X154),co-(X155),co-(X156),co-(X157),co-(X158),co-(X18),co-(X84),antenna,co-domino,co-fish,eiffeltower,longhorn,odd-hole)-free   probe split 
See also: X156 co-(X138) X84 co-(X136) co-(X148) co-(X146) co-(X144) P6 2P3 co-(X142) co-(X140) co-(X150) X152 X132 X155 odd anti-hole X158 co-longhorn X18 co-(X46) co-(X129) co-(X30) co-antenna co-(X127) co-(X139) co-(X137) co-(X149) co-(X135) co-(X147) co-(X133) co-(X145) X154 co-(X131) co-(X143) X134 fish co-(X141) co-(X151) X157 co-eiffeltower 3K2 C6 X130 co-(X11) co-(X35) co-XF62n+3 X153 co-XF12n+3 domino C4 cup P2 K2,3 co-(X128)

Inclusions

Minimal superclasses:  Berge   K2,3-free   P6-free   cal C(G)-perfect   (co-(X30),co-(XZ1),co-(XZ4),co-longhorn)-free   co-P4-brittle   domino-free   hole-free   kernel solvable   (odd anti-hole,odd-hole)-free   odd-hole-free   perfect   perfectly 1-transversable 
Maximal subclasses:  (1,1)-colorable   (2,0)-colorable   (2,0)-colorable cap chordal   (2K2,C4,C5,S3,net)-free   (2K2,C4,C5)-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,odd anti-cycle)-free   (S3,net)-free cap split   (co-(P7),co-(star1,2,3),odd anti-cycle)-free   (co-(star1,2,3),co-(sunlet4),odd anti-cycle)-free   (anti-hole,co-domino,odd anti-cycle)-free   chordal cap co-chordal   co-bipartite   co-probe threshold   odd anti-cycle-free   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
     From the complement .



Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from (2K2,co-(C6),odd anti-cycle)-free 
     From the complement .


Unbounded from co-comparability graphs of posets of interval dimension 2, height 1 
     See  comparability graphs of posets of interval dimension 2, height 1  .




Unbounded from split  [1176]




Unbounded from co-bipartite 
     See  bipartite  .


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 from perfect  [476]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

See also : Weighted independent set

Algorithms for Domination

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