genus

tags: topology

equivalent to: genus

providers: ISGCI

Relations

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.