ISGCI project home  All classes  Smallgraphs

Graphclass: (2K3,2K3 + e,co-(A),co-(H),co-(X45),co-(XZ5),co-domino)-free

Complement classes:  (A,H,K3,3,K3,3-e,X45,XZ5,domino)-free 
See also: co-domino co-(H) co-(A) 2K3 + e 2K3 co-(XZ5) co-(X45)

Inclusions

Minimal superclasses:  (2K3,X42,co-(A),co-(H),co-(X45),co-(X46),co-(X47),co-(X48),co-(X49),co-(X50),co-(X51),co-(X52),co-(X53),co-(X54),co-(X55),co-(X56),co-(X57))-free   co-(BW3)-free 
Maximal subclasses:  (0,2)-colorable   (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(X85))-free   (2K2,C4,C5,S3,X159,X160,co-(H),co-rising sun,net)-free   (2K2,P4)-free   (2K3,2K3 + e,3K1,co-(A),co-(H),co-(T2),co-(X18),co-(X45),co-domino)-free   (2K3,2P3,C4,K3 cup P3,P4)-free   (A,C4 cup 2K1,P2 cup P3,R,co-(K5 - e),co-(W5),co-claw,twin-C5,twin-house)-free   (C5,K2 cup K3,K2,3,P,P2 cup P3,P5,co-(P),co-(P2 cup P3),co-fork,fork,house)-free   C5-free cap matrogenic   (S3,co-claw)-free   XC9-free   (co-(W4),co-claw)-free   bipartite   bisplit cap triangle-free   (claw,co-claw)-free   (co-claw,house)-free   (co-claw,odd anti-hole)-free   (co-claw,odd-hole)-free   co-interval cap cograph   co-trivially perfect   matrogenic   matroidal   odd-cycle-free   perfect cap triangle-free   probe threshold cap split   triangle-free 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:NP-completedetails
Independent set:NP-completedetails
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 bipartite permutation  [1182]
Unbounded from (2K2,C5,co-(C6),co-(C7),co-(C8),co-claw,co-diamond)-free 
     From the complement .


Unbounded from Hn,q grid  [1176]
Unbounded from (2K2,co-(X91),co-claw)-free 
     From the complement .




Unbounded from (co-(Cn+4),co-XF2n+1,co-XF3n,co-claw)-free 
     From the complement .





Unbounded from (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(X85))-free 
     From the complement .


Unbounded from (S3,co-(Cn+4),co-claw,net)-free 
     From the complement .






Unbounded from (co-(W4),co-claw)-free 
     From the complement .


Unbounded from (co-(Cn+4),co-claw)-free 
     From the complement .

Unbounded from (S3,co-(Cn+4),co-claw)-free 
     From the complement .

Unbounded from (co-(W4),co-claw,co-gem)-free 
     From the complement .



Unbounded from C4-free cap C6-free cap bipartite  [1183]


Unbounded from (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(K1,4),co-(X85))-free 
     From the complement .


Unbounded from grid  [1177]
Unbounded from (co-claw,co-diamond)-free 
     From the complement .








Unbounded from (A,C4 cup 2K1,P2 cup P3,R,co-(K5 - e),co-(W5),co-claw,twin-C5,twin-house)-free 
     From the complement .







Unbounded from (S3,co-(Cn+4),co-(S3 cup K1),co-claw)-free 
     From the complement .





Unbounded from (co-(XC11),co-claw,co-diamond)-free 
     From the complement .

Unbounded from (2K2,4K1,co-claw,co-diamond)-free 
     From the complement .






See also : Cliquewidth expression

Algorithms for Weighted independent set

See also : Cliquewidth expression : Independent set

Algorithms for Independent set

NP-complete from 2-subdivision cap planar 
      2-subdivision cap planar  are precisely the  2-subdivision  graphs of  planar  graphs.

NP-complete from 2-subdivision 
     From Poljak's [1111] construction (which is a 2-subdivision). See also [453]

NP-complete from (C4,C5,C6,C7,C8,H,X85,triangle)-free cap K1,4-free 
     Contains the  2-subdivision  of graphs of max. degree 3. See also  planar of degree 3  .

See also : Weighted independent set

Algorithms for Domination

NP-complete from chordal bipartite  [1156]
NP-complete from bipartite  [1142]
NP-complete from partial grid  [1162] [630]
NP-complete from domination perfect cap triangle-free  [1096]
See also : Cliquewidth expression