genus
tags: topology
equivalent to: genus
providers: ISGCI
Relations
Other | Relation from | Relation to |
---|---|---|
acyclic chromatic number | exclusion | upper bound |
arboricity | exclusion | upper bound |
average degree | exclusion | upper bound |
average distance | exclusion | exclusion |
bandwidth | exclusion | exclusion |
bipartite | unbounded | exclusion |
bipartite number | exclusion | unknown to HOPS |
bisection bandwidth | exclusion | exclusion |
block | unbounded | exclusion |
book thickness | exclusion | upper bound |
boolean width | exclusion | exclusion |
bounded components | unknown to HOPS | exclusion |
boxicity | exclusion | upper bound |
branch width | exclusion | exclusion |
c-closure | exclusion | exclusion |
carving-width | exclusion | exclusion |
chordal | unbounded | exclusion |
chordality | exclusion | upper bound |
chromatic number | exclusion | upper bound |
clique cover number | exclusion | exclusion |
clique-tree-width | exclusion | exclusion |
clique-width | exclusion | exclusion |
cluster | unbounded | exclusion |
co-cluster | unbounded | exclusion |
cograph | unbounded | exclusion |
complete | unbounded | exclusion |
connected | unbounded | unknown to HOPS |
cutwidth | exclusion | exclusion |
cycle | constant | exclusion |
cycles | constant | exclusion |
d-path-free | exclusion | exclusion |
degeneracy | exclusion | upper bound |
degree treewidth | exclusion | exclusion |
diameter | exclusion | exclusion |
diameter+max degree | unknown to HOPS | exclusion |
disjoint cycles | constant | exclusion |
distance to bipartite | exclusion | exclusion |
distance to block | exclusion | exclusion |
distance to bounded components | exclusion | exclusion |
distance to chordal | exclusion | exclusion |
distance to cluster | exclusion | exclusion |
distance to co-cluster | exclusion | exclusion |
distance to cograph | exclusion | exclusion |
distance to complete | exclusion | exclusion |
distance to edgeless | exclusion | exclusion |
distance to forest | exclusion | exclusion |
distance to interval | exclusion | exclusion |
distance to linear forest | exclusion | exclusion |
distance to maximum degree | exclusion | exclusion |
distance to outerplanar | exclusion | exclusion |
distance to perfect | exclusion | exclusion |
distance to planar | exclusion | exclusion |
distance to stars | exclusion | exclusion |
domatic number | exclusion | upper bound |
domination number | exclusion | exclusion |
edge clique cover number | exclusion | exclusion |
edge connectivity | exclusion | upper bound |
edgeless | constant | exclusion |
feedback edge set | upper bound | exclusion |
feedback vertex set | exclusion | exclusion |
forest | constant | exclusion |
girth | exclusion | exclusion |
grid | constant | exclusion |
h-index | exclusion | exclusion |
inf-flip-width | exclusion | exclusion |
interval | unbounded | exclusion |
iterated type partitions | exclusion | exclusion |
linear clique-width | exclusion | exclusion |
linear forest | constant | exclusion |
linear NLC-width | exclusion | exclusion |
linear rank-width | exclusion | exclusion |
maximum clique | exclusion | upper bound |
maximum degree | exclusion | exclusion |
maximum independent set | exclusion | exclusion |
maximum induced matching | exclusion | exclusion |
maximum leaf number | upper bound | exclusion |
maximum matching | exclusion | exclusion |
maximum matching on bipartite graphs | unknown to HOPS | exclusion |
mim-width | exclusion | unknown to HOPS |
minimum degree | exclusion | upper bound |
mm-width | exclusion | exclusion |
modular-width | exclusion | exclusion |
module-width | exclusion | exclusion |
neighborhood diversity | exclusion | exclusion |
NLC-width | exclusion | exclusion |
NLCT-width | exclusion | exclusion |
odd cycle transversal | exclusion | exclusion |
outerplanar | constant | exclusion |
path | constant | exclusion |
pathwidth | exclusion | exclusion |
pathwidth+maxdegree | exclusion | exclusion |
perfect | unbounded | exclusion |
planar | constant | exclusion |
radius-r flip-width | exclusion | upper bound |
rank-width | exclusion | exclusion |
shrub-depth | exclusion | exclusion |
sim-width | exclusion | unknown to HOPS |
star | constant | exclusion |
stars | constant | exclusion |
topological bandwidth | exclusion | exclusion |
tree | constant | exclusion |
tree-independence number | exclusion | unknown to HOPS |
treedepth | exclusion | exclusion |
treelength | exclusion | unknown to HOPS |
treewidth | exclusion | exclusion |
twin-cover number | exclusion | exclusion |
twin-width | exclusion | upper bound |
vertex connectivity | unknown to HOPS | unknown to HOPS |
vertex cover | exclusion | exclusion |
vertex integrity | exclusion | exclusion |
Results
- 2024 Twin-width of graphs on surfaces by Kráľ, Pekárková, Štorgel
- page 18 : genus upper bounds twin-width by a linear function – The twin-width of every graph $G$ of Euler genus $g \ge 1$ is at most … $18 \sqrt{47g}+O(1)$.
- 2022 Expanding the Graph Parameter Hierarchy by Tran
- page 34 : bounded c-closure does not imply bounded genus – Proposition 5.6. $c$-Closure is incomparable to Genus.
- page 34 : bounded genus does not imply bounded c-closure – Proposition 5.6. $c$-Closure is incomparable to Genus.
- page 37 : genus upper bounds twin-width by a linear function – Proposition 6.3. Genus strictly upper bounds Twin-width.
- page 37 : bounded twin-width does not imply bounded genus – Proposition 6.3. Genus strictly upper bounds Twin-width.
- 2019 The Graph Parameter Hierarchy by Sorge
- page 8 : genus upper bounds acyclic chromatic number by a linear function – Lemma 4.8 ([3]). The accylic chromatic number $\chi_a$ is upper bounded by the genus $g$. We have $\chi_a \le 4g+4$.
- page 10 : feedback edge set upper bounds genus by a linear function – Lemma 4.19. The feedback edge set number $f$ upper bounds the genus $g$. We have $g \le f$.
- 1994 Genus g Graphs Have Pagenumber O(√g) by Malitz
- page 24 : genus upper bounds book thickness by a linear function – Theorem 5.1. Genus $g$ graphs have pagenumber $O(\sqrt{g})$.
- Comparing Graph Parameters by Schröder
- page 23 : bounded genus does not imply bounded clique-width – Proposition 3.17
- page 24 : bounded vertex cover does not imply bounded genus – Proposition 3.18
- page 26 : bounded genus does not imply bounded distance to perfect – Proposition 3.24
- page 30 : bounded bandwidth does not imply bounded genus – Proposition 3.27
- page 33 : bounded genus does not imply bounded distance to planar – Proposition 3.34
- unknown source
- feedback edge set upper bounds genus by a linear function – Removing $k$ edges creates a forest that is embeddable into the plane. We now add one handle for each of the $k$ edges to get embedding into $k$-handle genus.
- graph class planar has constant genus
- https://en.wikipedia.org/wiki/Genus_(mathematics)#Graph_theory
- genus – The genus of a graph is the minimal integer $n$ such that the graph can be drawn without crossing itself on a sphere with $n$ handles.