# Graphclass: partial grid

Definition:

A graph is a partial grid iff it is an arbitrary subgraph (not necessarily induced) of a grid .

## 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 Polynomial [+]Details
Cliquewidth Unbounded [+]Details
Cliquewidth expression Unbounded or NP-complete [+]Details
Colourability Linear [+]Details
Cutwidth NP-complete [+]Details
Domination NP-complete [+]Details
Feedback vertex set Unknown to ISGCI [+]Details
Hamiltonian cycle NP-complete [+]Details
Hamiltonian path NP-complete [+]Details
Independent set Polynomial [+]Details
Recognition NP-complete [+]Details
Treewidth Unknown to ISGCI [+]Details
Weighted clique Linear [+]Details
Weighted feedback vertex set Unknown to ISGCI [+]Details
Weighted independent set Polynomial [+]Details