ISGCI project home  All classes  Smallgraphs

Graphclass: 3-mino

References: [1279]
Equivalent classes:  (4-fan,K1,4,W4,W5,co-(A cup K1),co-(co-fork cup K1),co-(gem cup K1),co-(net cup K1))-free   line graphs of Helly hypergraphs of rank 3 
Complement classes:  (A cup K1,co-(K1,4),co-(W4),co-(W5),co-4-fan,co-fork cup K1,gem cup K1,net cup K1)-free 
Related classes:  domino 

Inclusions

Minimal superclasses:  3-interval   K1,4-free 
Maximal subclasses:  (K1,4,diamond)-free   (W4,claw,gem)-free   XC12-free   domino   line graphs of linear hypergraphs of rank 3   line graphs of multigraphs without triangles 

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 from (4-fan,K1,4,W4,W5,co-(A cup K1),co-(co-fork cup K1),co-(gem cup K1),co-(net cup K1))-free 
     Finite forbidden subgraph characterization


Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from Hn,q grid  [1176]
Unbounded from Fn grid  [1176]
Unbounded from (C4,K4,claw,diamond)-free  [1183]
See also : Cliquewidth expression

Algorithms for Weighted independent set

NP-complete from (K1,4,diamond)-free  [1115]
NP-complete from planar of degree 3  [421]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

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 planar of degree 3  [420]
See also : Cliquewidth expression