| CARVIEW |
Select Language
HTTP/2 200
server: nginx
date: Wed, 31 Dec 2025 04:04:10 GMT
content-type: text/html
last-modified: Sun, 16 Nov 2025 14:16:20 GMT
etag: W/"3327-643b6dfeaa6f5"
content-encoding: gzip
Information System on Graph Classes and their Inclusions
Clique
Clique cover
Colourability
Domination
Feedback vertex set
Graph isomorphism
Hamiltonian cycle
Hamiltonian path
Independent set
Maximum cut
Monopolarity
Polarity
Recognition
Weighted clique
Weighted feedback vertex set
Weighted independent set
book thickness decomposition
booleanwidth decomposition
cliquewidth decomposition
cutwidth decomposition
treewidth decomposition
bandwidth
book thickness
booleanwidth
branchwidth
carvingwidth
chromatic number
cliquewidth
cochromatic number
cutwidth
degeneracy
diameter
distance to block
distance to clique
distance to cluster
distance to co-cluster
distance to cograph
distance to linear forest
distance to outerplanar
genus
max-leaf number
maximum clique
maximum degree
maximum independent set
maximum induced matching
maximum matching
minimum clique cover
minimum dominating set
pathwidth
rankwidth
tree depth
treewidth
vertex cover
Information System on Graph Classes and their Inclusions
What is ISGCI?
ISGCI is an encyclopaedia of graphclasses with an accompanying java application that helps you to research what's known about particular graph classes. You can:- check the relation between graph classes and get a witness for the result
- draw clear inclusion diagrams
- colour these diagrams according to the complexity of selected problems
- find the P/NP boundary for a problem
- save your diagrams as Postscript, GraphML or SVG files
- find references on classes, inclusions and algorithms
Problems
3-ColourabilityClique
Clique cover
Colourability
Domination
Feedback vertex set
Graph isomorphism
Hamiltonian cycle
Hamiltonian path
Independent set
Maximum cut
Monopolarity
Polarity
Recognition
Weighted clique
Weighted feedback vertex set
Weighted independent set
book thickness decomposition
booleanwidth decomposition
cliquewidth decomposition
cutwidth decomposition
treewidth decomposition
Parameters
acyclic chromatic numberbandwidth
book thickness
booleanwidth
branchwidth
carvingwidth
chromatic number
cliquewidth
cochromatic number
cutwidth
degeneracy
diameter
distance to block
distance to clique
distance to cluster
distance to co-cluster
distance to cograph
distance to linear forest
distance to outerplanar
genus
max-leaf number
maximum clique
maximum degree
maximum independent set
maximum induced matching
maximum matching
minimum clique cover
minimum dominating set
pathwidth
rankwidth
tree depth
treewidth
vertex cover
- ISGCI home
- The Java application
- All classes
- References
- Smallgraphs
- About ISGCI
- Screenshots
- News
- FAQ
- Contact ✉
- Impressum
Database contents
| 1688 | classes |
| 242084 | inclusions |
| 28884 | complexities |
| 51804 | bounds |
updated 2025-11-16
Latest news
- 2025-11-16 Added pages for speed and self-complimentariness.
- 2024-07-22 Java application instructions updated.
- 2018-12-30 Added support for speed.
https://www.graphclasses.org
Information System on Graph Classes and their Inclusions (ISGCI)
by H.N. de Ridder et al. 2001-2014
Information System on Graph Classes and their Inclusions (ISGCI)
by H.N. de Ridder et al. 2001-2014