ISGCI project home  All classes  Smallgraphs

Graphclass: (2K2,co-diamond)-free

Complement classes:  (C4,diamond)-free   weakly geodetic 
See also: co-diamond 2K2

Inclusions

Minimal superclasses:  (2K2,A,H)-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-diamond)-free   N*   (P5,co-(X38),co-gem)-free   (P5,co-domino,co-gem)-free   (P5,cricket)-free   (P5,fork)-free   (co-(P),fork)-free   co-(XC10)-free 
Maximal subclasses:  (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(K1,4),co-(X85))-free   (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(X85))-free   (2K2,4K1,co-claw,co-diamond)-free   (2K2,C5,co-(C6),co-(C7),co-(C8),co-claw,co-diamond)-free   (2K2,co-(C6),odd anti-cycle)-free   (co-(Cn+4),co-diamond)-free   co-(P3)-free   (co-(T3),co-(X81),co-cycle)-free   co-cycle-free 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
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

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

Unbounded from (2K2,C5,co-(C6),co-(C7),co-(C8),co-claw,co-diamond)-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 (2K2,3K1,C5,co-(C6),co-(C7),co-(C8),co-(H),co-(K1,4),co-(X85))-free 
     From the complement .

Unbounded
     From the complement .











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


See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial [O(VE)] from (co-(P),fork)-free  [1125]
Polynomial [O(VE)] from (P5,fork)-free  [1125]
Polynomial from nK2-free, fixed n  [1102]
Polynomial from (P5,cricket)-free  [1110]
Polynomial from K2 cup claw-free  [1290]
Polynomial [O(VE)] from co-gem-free 
     Because for all v: G[\co{N}(v)] is P_4-free

Polynomial from fork-free  [1099]
Polynomial from (P5,X82,X83)-free  [1246]
Polynomial from 2K2-free  [1160]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Polynomial from co-hereditary clique-Helly  [1298]
See also : Weighted independent set

Algorithms for Domination

See also : Cliquewidth expression