edgeless
providers: ISGCI
Definition: Contains no edges.
Relations
Other | Relation from | Relation to | |
---|---|---|---|
acyclic chromatic number | ■ | avoids | upper bound |
admissibility | ■ | avoids | upper bound |
arboricity | ■ | avoids | upper bound |
average degree | ■ | avoids | upper bound |
average distance | ■ | avoids | upper bound |
bandwidth | ■ | avoids | unknown to HOPS |
bipartite | ■ | avoids | upper bound |
bipartite number | ■ | avoids | exclusion |
bisection bandwidth | ■ | avoids | unknown to HOPS |
block | ■ | avoids | upper bound |
book thickness | ■ | avoids | upper bound |
boolean width | ■ | avoids | upper bound |
bounded components | ■ | avoids | upper bound |
bounded expansion | ■ | avoids | upper bound |
boxicity | ■ | avoids | upper bound |
branch width | ■ | avoids | upper bound |
c-closure | ■ | avoids | upper bound |
carving-width | ■ | avoids | upper bound |
chi-bounded | ■ | avoids | upper bound |
chordal | ■ | avoids | upper bound |
chordality | ■ | avoids | upper bound |
chromatic number | ■ | avoids | upper bound |
clique cover number | ■ | avoids | exclusion |
clique-tree-width | ■ | avoids | upper bound |
clique-width | ■ | avoids | upper bound |
cluster | ■ | avoids | inclusion |
co-cluster | ■ | avoids | inclusion |
cograph | ■ | avoids | upper bound |
complete | ■ | avoids | exclusion |
connected | ■ | avoids | avoids |
contraction complexity | ■ | avoids | upper bound |
cutwidth | ■ | avoids | upper bound |
cycle | ■ | unknown to HOPS | exclusion |
cycles | ■ | avoids | exclusion |
d-admissibility | ■ | avoids | upper bound |
d-path-free | ■ | avoids | upper bound |
degeneracy | ■ | avoids | upper bound |
degree treewidth | ■ | avoids | upper bound |
diameter | ■ | avoids | upper bound |
diameter+max degree | ■ | avoids | upper bound |
distance to bipartite | ■ | avoids | upper bound |
distance to block | ■ | avoids | upper bound |
distance to bounded components | ■ | avoids | upper bound |
distance to chordal | ■ | avoids | upper bound |
distance to cluster | ■ | avoids | upper bound |
distance to co-cluster | ■ | avoids | upper bound |
distance to cograph | ■ | avoids | upper bound |
distance to complete | ■ | avoids | exclusion |
distance to edgeless | ■ | avoids | upper bound |
distance to forest | ■ | avoids | upper bound |
distance to interval | ■ | avoids | upper bound |
distance to linear forest | ■ | avoids | upper bound |
distance to maximum degree | ■ | avoids | upper bound |
distance to outerplanar | ■ | avoids | upper bound |
distance to perfect | ■ | avoids | upper bound |
distance to planar | ■ | avoids | upper bound |
distance to stars | ■ | avoids | upper bound |
domatic number | ■ | avoids | upper bound |
domination number | ■ | avoids | exclusion |
domino treewidth | ■ | avoids | upper bound |
edge clique cover number | ■ | avoids | unknown to HOPS |
edge connectivity | ■ | avoids | upper bound |
edge-cut width | ■ | avoids | upper bound |
edge-treewidth | ■ | avoids | upper bound |
edgeless | ■ | equal | equal |
excluded minor | ■ | avoids | upper bound |
excluded planar minor | ■ | unknown to HOPS | unknown to HOPS |
excluded top-minor | ■ | avoids | upper bound |
feedback edge set | ■ | avoids | upper bound |
feedback vertex set | ■ | avoids | upper bound |
flip-width | ■ | avoids | upper bound |
forest | ■ | avoids | upper bound |
genus | ■ | avoids | upper bound |
grid | ■ | avoids | exclusion |
h-index | ■ | avoids | upper bound |
interval | ■ | avoids | upper bound |
iterated type partitions | ■ | avoids | upper bound |
linear clique-width | ■ | avoids | upper bound |
linear forest | ■ | avoids | inclusion |
linear NLC-width | ■ | avoids | upper bound |
linear rank-width | ■ | avoids | upper bound |
maximum clique | ■ | avoids | upper bound |
maximum degree | ■ | avoids | upper bound |
maximum independent set | ■ | avoids | exclusion |
maximum induced matching | ■ | avoids | upper bound |
maximum leaf number | ■ | avoids | unknown to HOPS |
maximum matching | ■ | avoids | upper bound |
maximum matching on bipartite graphs | ■ | avoids | upper bound |
merge-width | ■ | avoids | upper bound |
mim-width | ■ | avoids | upper bound |
minimum degree | ■ | avoids | upper bound |
mm-width | ■ | avoids | upper bound |
modular-width | ■ | avoids | upper bound |
module-width | ■ | avoids | upper bound |
monadically dependent | ■ | avoids | upper bound |
monadically stable | ■ | avoids | upper bound |
neighborhood diversity | ■ | avoids | upper bound |
NLC-width | ■ | avoids | upper bound |
NLCT-width | ■ | avoids | upper bound |
nowhere dense | ■ | avoids | upper bound |
odd cycle transversal | ■ | avoids | upper bound |
outerplanar | ■ | unknown to HOPS | unknown to HOPS |
overlap treewidth | ■ | avoids | upper bound |
path | ■ | avoids | exclusion |
pathwidth | ■ | avoids | upper bound |
pathwidth+maxdegree | ■ | avoids | upper bound |
perfect | ■ | avoids | upper bound |
planar | ■ | avoids | unknown to HOPS |
radius-inf flip-width | ■ | avoids | upper bound |
radius-r flip-width | ■ | avoids | upper bound |
rank-width | ■ | avoids | upper bound |
series-parallel | ■ | unknown to HOPS | unknown to HOPS |
shrub-depth | ■ | avoids | upper bound |
sim-width | ■ | avoids | upper bound |
size | ■ | avoids | exclusion |
slim tree-cut width | ■ | avoids | upper bound |
sparse twin-width | ■ | avoids | upper bound |
star | ■ | avoids | exclusion |
stars | ■ | avoids | inclusion |
strong coloring number | ■ | avoids | upper bound |
strong d-coloring number | ■ | avoids | upper bound |
strong inf-coloring number | ■ | avoids | upper bound |
topological bandwidth | ■ | avoids | unknown to HOPS |
tree | ■ | avoids | exclusion |
tree-cut width | ■ | avoids | upper bound |
tree-independence number | ■ | avoids | upper bound |
tree-partition-width | ■ | avoids | upper bound |
treebandwidth | ■ | avoids | upper bound |
treedepth | ■ | avoids | upper bound |
treelength | ■ | avoids | upper bound |
treespan | ■ | avoids | upper bound |
treewidth | ■ | avoids | upper bound |
twin-cover number | ■ | avoids | upper bound |
twin-width | ■ | avoids | upper bound |
vertex connectivity | ■ | avoids | unknown to HOPS |
vertex cover | ■ | avoids | upper bound |
vertex integrity | ■ | avoids | upper bound |
weak coloring number | ■ | avoids | upper bound |
weak d-coloring number | ■ | avoids | upper bound |
weak inf-coloring number | ■ | avoids | upper bound |
weakly sparse | ■ | avoids | upper bound |
weakly sparse and merge width | ■ | avoids | upper bound |
Results
- 2017 Graph Theory by Diestel
- page 5 : edgeless – A vertex of degree $0$ is \emph{isolated}.
- assumed
- graph classes that are edgeless have contained in linear forest
- graph class linear forest is not edgeless
- graph classes that are edgeless have contained in stars
- graph class stars is not edgeless
- graph classes that are edgeless have contained in co-cluster
- graph class co-cluster is not edgeless
- graph classes that are edgeless have contained in cluster
- graph class cluster is not edgeless
- edgeless upper bounds distance to edgeless by a constant – by definition
- edgeless upper bounds bounded components by a constant – By definition
- graph classes that are edgeless are not connected – By definition
- graph classes that are edgeless do not have contained in cycles – By definition
- edgeless is equivalent to edgeless – assumed
- unknown source
- edgeless upper bounds vertex cover by a constant
- graph classes that are edgeless are not constant domination number
- edgeless upper bounds maximum matching by a constant