3
$\begingroup$

Suppose a simple undirected graph $G$ with $n$ vertices has (minimum) genus $g$. What is the genus of its complement?

My intuitive guess is that the answer is something like

$$\text{genus of }K_n - g$$

but I wasn't able to find any information on this topic online. Is there a known solution to this problem?

This is my first time on MathOverflow, so I apologize if my question is missing something -- thanks for the help :)

Improve this question
$\endgroup$
6
  • $\begingroup$ Can you add the definition of genus of a graph (or a link)? $\endgroup$
    – M. Winter
    Commented Jun 19, 2020 at 6:25
  • 2
    $\begingroup$ If $G$ is any graph on five vertices, other than $K_5$ or its complement, then both $G$ and its complement are planar, while $K_5$ isn't. $\endgroup$
    – Gerry Myerson
    Commented Jun 19, 2020 at 7:20
  • 2
    $\begingroup$ @M.Winter I take it to be the minimum $g$ such that the graph has a 2-cell embedding into a surface of genus $g$. $\endgroup$
    – Gerry Myerson
    Commented Jun 19, 2020 at 7:22
  • 1
    $\begingroup$ Your intuitive guess can be off by something linear in $n$: clearly $K_{n-2,2}$ is planar, its complement $K_{n-2}$ (plus an isolated edge) has genus $(n-5)(n-6)/12$, which is $\approx n/3$ less than the genus of $K_n$. $\endgroup$
    – Florian Lehner
    Commented Jun 19, 2020 at 9:17
  • $\begingroup$ To get a feeling and some (counter-)examples one could play around with known coloring results and the coloring-genus-connection given by the Hadwiger conjecture (now a theorem). $\endgroup$
    – M. Winter
    Commented Jun 19, 2020 at 9:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .