cluster
equivalent to: cluster
providers: ISGCI
Relations
Other | Relation from | Relation to |
---|---|---|
acyclic chromatic number | exclusion | unbounded |
arboricity | exclusion | unbounded |
average degree | exclusion | unbounded |
average distance | exclusion | constant |
bandwidth | exclusion | unbounded |
bipartite | exclusion | exclusion |
bipartite number | exclusion | constant |
bisection bandwidth | exclusion | unbounded |
block | exclusion | inclusion |
book thickness | exclusion | unbounded |
boolean width | exclusion | constant |
bounded components | exclusion | unbounded |
boxicity | exclusion | constant |
branch width | exclusion | unbounded |
c-closure | exclusion | unknown to HOPS |
carving-width | exclusion | unbounded |
chordal | exclusion | inclusion |
chordality | exclusion | constant |
chromatic number | exclusion | unbounded |
clique cover number | exclusion | unbounded |
clique-tree-width | exclusion | constant |
clique-width | exclusion | constant |
co-cluster | exclusion | unknown to HOPS |
cograph | exclusion | unknown to HOPS |
complete | inclusion | exclusion |
connected | exclusion | unknown to HOPS |
cutwidth | exclusion | unbounded |
cycle | exclusion | exclusion |
cycles | exclusion | exclusion |
d-path-free | exclusion | unbounded |
degeneracy | exclusion | unbounded |
degree treewidth | exclusion | unbounded |
diameter | exclusion | constant |
diameter+max degree | exclusion | unbounded |
disjoint cycles | exclusion | exclusion |
distance to bipartite | exclusion | unbounded |
distance to block | exclusion | constant |
distance to bounded components | exclusion | unbounded |
distance to chordal | exclusion | constant |
distance to cluster | exclusion | constant |
distance to co-cluster | exclusion | unknown to HOPS |
distance to cograph | exclusion | unknown to HOPS |
distance to complete | exclusion | unbounded |
distance to edgeless | unknown to HOPS | unbounded |
distance to forest | exclusion | unbounded |
distance to interval | exclusion | constant |
distance to linear forest | exclusion | unbounded |
distance to maximum degree | exclusion | unbounded |
distance to outerplanar | exclusion | unbounded |
distance to perfect | exclusion | constant |
distance to planar | exclusion | unknown to HOPS |
distance to stars | unknown to HOPS | unbounded |
domatic number | exclusion | unbounded |
domination number | exclusion | unbounded |
edge clique cover number | exclusion | unknown to HOPS |
edge connectivity | exclusion | unbounded |
edgeless | inclusion | exclusion |
feedback edge set | exclusion | unbounded |
feedback vertex set | exclusion | unbounded |
forest | exclusion | exclusion |
genus | exclusion | unbounded |
girth | exclusion | constant |
grid | exclusion | exclusion |
h-index | exclusion | unbounded |
inf-flip-width | exclusion | constant |
interval | exclusion | inclusion |
iterated type partitions | exclusion | unknown to HOPS |
linear clique-width | exclusion | constant |
linear forest | exclusion | exclusion |
linear NLC-width | exclusion | constant |
linear rank-width | exclusion | constant |
maximum clique | exclusion | unbounded |
maximum degree | exclusion | unbounded |
maximum independent set | exclusion | unbounded |
maximum induced matching | exclusion | unknown to HOPS |
maximum leaf number | exclusion | unbounded |
maximum matching | unknown to HOPS | unbounded |
maximum matching on bipartite graphs | unknown to HOPS | unbounded |
mim-width | exclusion | constant |
minimum degree | exclusion | unbounded |
mm-width | exclusion | unbounded |
modular-width | exclusion | constant |
module-width | exclusion | constant |
neighborhood diversity | exclusion | unknown to HOPS |
NLC-width | exclusion | constant |
NLCT-width | exclusion | constant |
odd cycle transversal | exclusion | unbounded |
outerplanar | exclusion | exclusion |
path | exclusion | exclusion |
pathwidth | exclusion | unbounded |
pathwidth+maxdegree | exclusion | unbounded |
perfect | exclusion | inclusion |
planar | exclusion | exclusion |
radius-r flip-width | exclusion | constant |
rank-width | exclusion | constant |
shrub-depth | exclusion | constant |
sim-width | exclusion | constant |
star | unknown to HOPS | exclusion |
stars | unknown to HOPS | exclusion |
topological bandwidth | exclusion | unbounded |
tree | exclusion | exclusion |
tree-independence number | exclusion | unknown to HOPS |
treedepth | exclusion | unbounded |
treelength | exclusion | constant |
treewidth | exclusion | unbounded |
twin-cover number | unknown to HOPS | constant |
twin-width | exclusion | constant |
vertex connectivity | unknown to HOPS | unknown to HOPS |
vertex cover | unknown to HOPS | unbounded |
vertex integrity | exclusion | unbounded |
Results
- assumed
- cluster – Disjoint union of complete graphs.
- cluster – Every connected component is a complete graph.
- cluster – Does not include path on three vertices as an induced subgraph.
- graph class complete is included in graph class cluster – by definition
- graph class cluster is included in graph class interval
- graph class interval is not included in graph class cluster
- graph class cluster is included in graph class block
- graph class block is not included in graph class cluster
- graph class edgeless is included in graph class cluster
- graph class cluster is not included in graph class edgeless
- graph class cluster has constant distance to cluster – by definition
- unknown source
- graph class cluster has constant twin-cover number
- graph class cluster has unbounded domination number