ISGCI project home  All classes  Smallgraphs

Graphclass: 2-interval

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

References: [1031] [472]
Related classes:  interval 

Inclusions

Minimal superclasses:  3-interval 
Maximal subclasses:  (0,2)-colorable cap chordal   (2K2,C4,C5,S3,co-rising sun,net,rising sun)-free   AT-free cap chordal   C4-free cap co-comparability   (Cn+4,T2,X31,XF2n+1,XF3n)-free   (Cn+4,diamond)-free   Halin   (K5 - e,W5,co-(A),co-(C4 cup 2K1),co-(P2 cup P3),co-(R),claw,co-twin-C5,co-twin-house)-free   (W4,claw,gem)-free   XC12-free   bipartite cap bridged   block   boxicity 1   caterpillar arboricity <= 2   chordal cap co-chordal cap co-comparability cap comparability   chordal cap co-comparability   chordal cap diamond-free   circular arc   (claw,diamond,odd-hole)-free   co-interval cap interval   cycle-free   domino   gridline   interval   line   line graphs of bipartite graphs   line graphs of multigraphs without triangles   outerplanar   partial grid   permutation cap split   planar of degree 3   ptolemaic cap weakly geodetic   split cap threshold signed   tree 

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 .



See also : Cliquewidth expression

Algorithms for Weighted independent set

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 (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