Definition:
A graph is a 2-interval iff it has an intersection model
whose objects consist of 2 intervals on a real line.
Recognition: | NP-complete | details |
Cliquewidth expression: | Unbounded or NP-complete | details |
Cliquewidth: | Unbounded | details |
Weighted independent set: | NP-complete | details |
Independent set: | NP-complete | details |
Domination: | NP-complete | details |
Algorithms for Recognition
NP-complete [1079]
Algorithms for Cliquewidth expression
See also : Cliquewidth :
Weighted independent set : Domination
Algorithms for Cliquewidth
Unbounded from grid
[1177]
Unbounded from Fn
grid [1176]
Unbounded from Hn,q
grid [1176]
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 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]
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
planar
2-subdivision
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
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 partial
grid [1162]
[630]
NP-complete from line
[1129]
NP-complete from planar
of degree 3 [420]
See also : Cliquewidth expression