ISGCI project home  All classes  Smallgraphs

Graphclass: 3-interval

Definition:
A graph is a 3-interval iff it has an intersection model whose objects consits of 3 intervals on a real line.

References: [1031] [472]

Inclusions

Maximal subclasses:  2-interval   3-mino   (4-fan,K1,4,W4,W5,co-(A cup K1),co-(co-fork cup K1),co-(gem cup K1),co-(net cup K1))-free   XC11-free   genus 0   line graphs of Helly hypergraphs of rank 3   partial bar visibility   planar   weak bar visibility 

Problems summary

Recognition:NP-completedetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:NP-completedetails
Independent set:NP-completedetails
Domination:NP-completedetails

Algorithms for Recognition

NP-complete [1079]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth


Unbounded from Hn,q grid  [1176]
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 Fn grid  [1176]

Unbounded from unit interval  [1177]


Unbounded from grid  [1177]
Unbounded from (C4,K4,claw,diamond)-free  [1183]

Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free 
     From the complement .

Unbounded from planar  [1174]


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 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 planar  [421]
     Even when the maximum degree is at most 6.

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 line  [1129]
NP-complete from planar of degree 3  [420]
NP-complete from partial grid  [1162] [630]
See also : Cliquewidth expression