ISGCI project home  All classes  Smallgraphs

Graphclass: (K2,3,P,hole)-free

Complement classes:  (K2 cup K3,co-(P),anti-hole)-free 
See also: P hole K2,3

Inclusions

Minimal superclasses:  (6,1)-even-chordal   BW3-free   K2,3-free   P-free   (X79,X80)-free   (co-(X30),co-(XZ1),co-(XZ4),co-longhorn)-free   domino-free   even-hole-free   hole-free   odd-hole-free 
Maximal subclasses:  (1,1)-colorable   (2,0)-colorable   (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,C4,C5,S3,net)-free   (2K2,C4,C5)-free   (2K3 + e,3K1,C5,co-(T2),co-(X18),co-(X94),co-domino)-free   (3K1,C5,K3 cup K4,co-(BW3),co-(K3,4-e),co-(T2),co-(X18),co-(X92),co-(X93))-free   (3K1,C5,K5 - e,co-(C6 cup K1),co-(C7),co-(K3,3 cup K1),co-(K3,3-e cup K1),co-(domino cup K1))-free   (3K1,C5,butterfly,diamond)-free   (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free   (C4,P4,dart)-free   (C4,P4)-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   Cn+4-free   (S3,net)-free cap split   (co-(P7),co-(star1,2,3),odd anti-cycle)-free   (co-(T3),co-(X81),co-cycle)-free   (co-(star1,2,3),co-(sunlet4),odd anti-cycle)-free   (anti-hole,co-domino,odd anti-cycle)-free   chordal   chordal cap co-chordal   chordal cap cograph   co-bipartite   co-cycle-free   cograph cap interval   comparability graphs of arborescence orders   intersection graph of nested intervals   matroidal   odd anti-cycle-free   quasi-threshold   split   superfragile   trivially perfect 

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


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 unit interval  [1177]

Unbounded from split  [1176]
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 co-bipartite 
     See  bipartite  .


Unbounded from chordal  [1174]

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

Algorithms for Independent set

See also : Weighted independent set

Algorithms for Domination

NP-complete from chordal  [1146]
NP-complete from undirected path  [1146]
NP-complete from split  [1144] [1145]
See also : Cliquewidth expression