Graphclass: proper interval

Definition:

A proper interval graph is an interval graph that has an intersection model in which no interval properly contains another.

This class is fixed under the clique operator. That is, proper interval = clique graphs of proper interval.

[1503] [777]

[+]Details

Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

[+]Details

[+]Details

[+]Details

Problems

3-Colourability Linear [+]Details
Clique Linear [+]Details
Clique cover Linear [+]Details
Cliquewidth Unbounded [+]Details
Cliquewidth expression Unbounded or NP-complete [+]Details
Colourability Linear [+]Details
Cutwidth Linear [+]Details
Domination Linear [+]Details
Feedback vertex set Linear [+]Details
Hamiltonian cycle Linear [+]Details
Hamiltonian path Linear [+]Details
Independent set Linear [+]Details
Recognition Linear [+]Details
Treewidth Polynomial [+]Details
Weighted clique Linear [+]Details
Weighted feedback vertex set Linear [+]Details
Weighted independent set Linear [+]Details