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.
Speed
[?]
The speed of a class $X$ is the function $n \mapsto |X_n|$, where $X_n$ is the set of $n$-vertex labeled graphs in $X$.
Depending on the rate of growths of the speed of the class, ISGCI
distinguishes the following values of the parameter: |
unknown | [+]Details |
acyclic chromatic number
[?]
The acyclic chromatic number
of a graph $G$ is the smallest size of a vertex partition $\{V_1,\dots,V_l\}$ such that each $V_i$ is an independent set and
for all $i,j$ that graph $G[V_i\cup V_j]$ does not contain a cycle.
|
Unbounded | [+]Details | |
bandwidth
[?]
The bandwidth
of a graph $G$ is the
shortest maximum "length" of an edge over all one dimensional
layouts of $G$.
Formally, bandwidth
is defined as
$\min_{i \colon V \rightarrow \mathbb{N}\;}\{\max_{\{u,v\}\in E\;}
\{|i(u)-i(v)|\}\mid i\text{ is injective}\}$.
|
Unbounded | [+]Details | |
book thickness
[?]
A book embedding of a graph $G$ is an embedding of $G$ on a collection of half-planes (called pages) having the same line
(called spine) as their boundary, such that the vertices all lie on the spine and there are no crossing edges. The book thickness
of a graph $G$ is the smallest number of pages over all book embeddings of $G$.
|
Unbounded | [+]Details | |
booleanwidth
[?]
Consider the following decomposition of a graph $G$ which is defined
as a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection
from $V(G)$ to the leaves of the tree $T$. The function
$\text{cut-bool} \colon 2^{V(G)} \rightarrow R$ is
defined as $\text{cut-bool}(A)$ := $\log_2|\{S \subseteq
V(G) \backslash A \mid \exists X \subseteq A \colon
S = (V(G) \backslash A) \cap \bigcup_{x \in X} N(x)\}|$.
Every edge $e$ in $T$
partitions the vertices $V(G)$ into $\{A_e,\overline{A_e}\}$ according
to the leaves of the two connected components of $T - e$.
The booleanwidth of the above decomposition $(T,L)$
is $\max_{e \in E(T)\;} \{ \text{cut-bool}(A_e)\}$.
The booleanwidth
of a graph $G$ is the
minimum booleanwidth of a decomposition of $G$ as above.
|
Unbounded | [+]Details | |
branchwidth
[?]
A branch decomposition of a graph $G$ is a pair $(T,\chi)$,
where $T$ is a binary tree and $\chi$ is a bijection, mapping leaves
of $T$ to edges of $G$. Any edge $\{u, v\}$ of the tree divides
the tree into two components and
divides the set of edges of $G$ into two parts $X, E \backslash X$,
consisting of edges mapped to the leaves of each component. The
width of the edge $\{u,v\}$ is the number of vertices of $G$ that is incident both with an edge in
$X$ and with an edge in $E \backslash X$. The width of the
decomposition $(T,\chi)$ is the maximum width of its edges. The
branchwidth
of the graph $G$ is the
minimum width over all branch-decompositions of $G$.
|
Unbounded | [+]Details | |
carvingwidth
[?]
Consider a decomposition $(T,\chi)$ of a graph $G$ where $T$
is a binary tree with $|V(G)|$ leaves and $\chi$ is a
bijection mapping the leaves of $T$ to the vertices of
$G$. Every edge $e \in E(T)$ of the tree $T$ partitions the
vertices of the graph $G$ into two parts $V_e$ and $V
\backslash V_e$ according to the leaves of the two connected
components in $T - e$. The width of an edge $e$ of the tree
is the number of edges of a graph $G$ that have exactly one
endpoint in $V_e$ and another endpoint in $V \backslash V_e$.
The width of the decomposition $(T,\chi)$ is the largest
width over all edges of the tree $T$. The
carvingwidth
of a graph is the
minimum width over all decompositions as above.
|
Unbounded | [+]Details | |
chromatic number
[?]
The chromatic number
of a graph is the minimum
number of colours needed to label all its vertices in
such a way that no two vertices with the same color are adjacent.
|
Unbounded | [+]Details | |
cliquewidth
[?]
The cliquewidth of a graph is the number of different labels
that is needed to construct the graph using the following
operations:
|
Unbounded | [+]Details | |
cutwidth
[?]
The cutwidth of a graph $G$ is the smallest integer $k$ such
that the vertices of $G$ can be arranged in a linear layout
$v_1, \ldots, v_n$ in such a way that for every $i = 1,
\ldots,n - 1$, there are at most $k$ edges with one endpoint
in $\{v_1, \ldots, v_i\}$ and the other in ${v_{i+1}, \ldots,
v_n\}$.
|
Unbounded | [+]Details | |
degeneracy
[?]
The degeneracy
of a graph $G$ is the
smallest integer $k$ such that each subgraph of $G$ contains a vertex
of degree at most $k$.
|
Unbounded | [+]Details | |
diameter
[?]
The diameter
of a graph $G$ is the
length of the longest shortest path between any two vertices in $G$.
|
Unbounded | [+]Details | |
distance to block
[?]
The distance to block
of a graph $G$ is the
size of a smallest vertex subset whose deletion makes $G$ a
block
graph.
|
Unbounded | [+]Details | |
distance to clique
[?]
Let $G$ be a graph. Its distance to clique
is the
minimum number of vertices that have to be deleted from $G$ in
order to obtain a clique.
|
Unbounded | [+]Details | |
distance to cluster
[?]
A cluster
is a disjoint union
of cliques. The
distance to cluster
of a graph $G$ is the size
of a smallest vertex subset whose deletion makes $G$ a
cluster
graph.
|
Unbounded | [+]Details | |
distance to co-cluster
[?]
The distance to co-cluster
of a graph is the
minimum number of vertices that have to be deleted to obtain a
co-cluster
graph.
|
Unbounded | [+]Details | |
distance to cograph
[?]
The distance to cograph
of a graph $G$ is
the minimum number of vertices that have to be deleted from $G$ in
order to obtain a cograph
.
|
Unbounded | [+]Details | |
distance to linear forest
[?]
The distance to linear forest
of a graph $G = (V, E)$ is
the size of a smallest subset $S$ of vertices, such that
$G[V \backslash S]$ is a disjoint union of paths and singleton
vertices.
|
Unbounded | [+]Details | |
distance to outerplanar
[?]
The distance to outerplanar
of a graph $G = (V,E)$ is
the minumum size of a vertex subset $X \subseteq V$, such that $G[V
\backslash X]$ is a outerplanar
graph.
|
Unbounded | [+]Details | |
genus
[?]
The genus $g$ of a graph $G$ is the minimum number of handles over
all surfaces on which $G$ can be embedded without edge crossings.
|
Unbounded | [+]Details | |
max-leaf number
[?]
The max-leaf number
of a graph $G$ is the
maximum number of leaves in a spanning tree of $G$.
|
Unbounded | [+]Details | |
maximum clique
[?]
The parameter maximum clique
of a graph $G$
is the largest number of vertices in a complete subgraph of $G$.
|
Unbounded | [+]Details | |
maximum degree
[?]
The maximum degree
of a graph $G$ is the
largest number of neighbors of a vertex in $G$.
|
Unbounded | [+]Details | |
maximum independent set
[?]
An independent set of a graph $G$ is a subset of pairwise non-adjacent
vertices. The parameter maximum independent set
of
graph $G$ is the size of a largest independent set in $G$.
|
Unbounded | [+]Details | |
maximum induced matching
[?]
For a graph $G = (V,E)$ an induced matching is an edge subset
$M \subseteq E$ that satisfies the following two conditions:
$M$ is a matching of the graph $G$ and there is no edge in $E
\backslash M$ connecting any two vertices belonging to edges
of the matching $M$. The parameter
maximum induced matching
of a graph $G$ is the
largest size of an induced matching in $G$.
|
Unbounded | [+]Details | |
maximum matching
[?]
A matching in a graph is a subset of pairwise disjoint edges
(any two edges that do not share an endpoint). The parameter
maximum matching
of a graph $G$ is the
largest size of a matching in $G$.
|
Unbounded | [+]Details | |
minimum clique cover
[?]
A clique cover of a graph $G = (V, E)$ is a partition $P$ of $V$
such that each part in $P$ induces a clique in $G$. The
minimum clique cover
of $G$ is the minimum number of
parts in a clique cover
of $G$. Note that the clique cover number of
a graph is exactly the chromatic number of its complement.
|
Unbounded | [+]Details | |
minimum dominating set
[?]
A dominating set of a graph $G$ is a subset $D$ of its vertices, such
that every vertex not in $D$ is adjacent to at least one member of
$D$. The parameter minimum dominating set
for graph
$G$ is the minimum number of vertices in a dominating set for $G$.
|
Unbounded | [+]Details | |
pathwidth
[?]
A path decomposition of a graph $G$ is a pair $(P,X)$ where $P$ is
a path with vertex set $\{1, \ldots, q\}$, and
$X = \{X_1,X_2, \ldots ,X_q\}$ is a family of vertex subsets of $V(G)$
such that:
|
Unbounded | [+]Details | |
rankwidth
[?]
Let $M$ be the $|V| \times |V|$ adjacency matrix of a graph $G$. The
cut rank of a set $A \subseteq V(G)$ is the rank of the submatrix of
$M$ induced by the rows of $A$ and the columns of $V(G) \backslash A$.
A rank decomposition of a graph $G$ is a pair $(T,L)$ where $T$ is a
binary tree and $L$ is a bijection from $V(G)$ to the leaves of the
tree $T$. Any edge $e$ in the tree $T$ splits $V(G)$ into two parts
$A_e, B_e$ corresponding to the leaves of the two connected components
of $T - e$. The width of an edge $e \in E(T)$ is the cutrank of $A_e$.
The width of the rank-decomposition $(T,L)$ is the maximum width of an
edge in $T$. The rankwidth
of the graph
$G$ is the minimum width of a rank-decomposition of $G$.
|
Unbounded | [+]Details | |
tree depth
[?]
A tree depth decomposition of a graph $G = (V,E)$ is a rooted
tree $T$ with the same vertices $V$, such that, for every
edge $\{u,v\} \in E$, either $u$ is an ancestor of $v$ or $v$
is an ancestor of $u$ in the tree $T$. The depth of $T$ is
the maximum number of vertices on a path from the root to any
leaf. The tree depth
of a graph
$G$ is the minimum depth among all tree depth decompositions.
|
Unbounded | [+]Details | |
treewidth
[?]
A tree decomposition of a graph $G$ is a pair $(T, X)$, where $T = (I,
F)$ is a tree, and $X = \{X_i \mid i \in I\}$ is a family of subsets
of $V(G)$ such that
The treewidth of a graph is the minimum width over all possible tree decompositions of the graph. |
Unbounded | [+]Details | |
vertex cover
[?]
Let $G$ be a graph. Its vertex cover
number is the minimum number of vertices that have to be deleted in
order to obtain an independent set.
|
Unbounded | [+]Details |
Problems in italics have no summary page and are only listed when ISGCI contains a result for the current class.
book thickness decomposition
[?]
|
Unknown to ISGCI | [+]Details | |||||
booleanwidth decomposition
[?]
|
Unknown to ISGCI | [+]Details | |||||
cliquewidth decomposition
[?]
|
Unknown to ISGCI | [+]Details | |||||
cutwidth decomposition
[?]
|
Unknown to ISGCI | [+]Details | |||||
treewidth decomposition
[?]
|
Polynomial | [+]Details |
3-Colourability
[?]
|
Polynomial | [+]Details | |||||
Clique
[?]
|
Polynomial | [+]Details | |||||
Clique cover
[?]
|
Polynomial | [+]Details | |||||
Colourability
[?]
|
Polynomial | [+]Details | |||||
Domination
[?]
|
Unknown to ISGCI | [+]Details | |||||
Feedback vertex set
[?]
|
Unknown to ISGCI | [+]Details | |||||
Graph isomorphism
[?]
|
Unknown to ISGCI | [+]Details | |||||
Hamiltonian cycle
[?]
|
NP-complete | [+]Details | |||||
Hamiltonian path
[?]
|
Unknown to ISGCI | [+]Details | |||||
Independent set
[?]
|
Polynomial | [+]Details | |||||
Maximum cut
[?]
(decision variant)
|
Unknown to ISGCI | [+]Details | |||||
Monopolarity
[?]
|
Polynomial | [+]Details | |||||
Polarity
[?]
|
Polynomial | [+]Details | |||||
Recognition
[?]
|
Unknown to ISGCI | [+]Details |
Weighted clique
[?]
|
Polynomial | [+]Details | |||||
Weighted feedback vertex set
[?]
|
Unknown to ISGCI | [+]Details | |||||
Weighted independent set
[?]
|
Polynomial | [+]Details | |||||
Weighted maximum cut
[?]
(decision variant)
|
NP-complete | [+]Details |