3
$\begingroup$

We know that planar graphs have $O(1)$ degree.

We know balanced (each color has same number of vertices) complete bipartite graphs have genus $O(n^2)$.

  1. If maximum and average degree are $O(n^\alpha)$ where $\alpha\in[0,1]$ then is genus also $O(n^\alpha)$?

  2. If maximum degree is $O(n^\alpha)$ where $\alpha\in[0,1]$ then is genus also $O(n^\alpha)$? (this is weaker than $1.$)

Improve this question
$\endgroup$
11
  • $\begingroup$ What is n? is it the coloring number of the graph? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Jul 23, 2017 at 6:46
  • $\begingroup$ The average degree is less then (or equal to) the maximum degree, so I guess I don't understand the difference between 1 and 2. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Jul 23, 2017 at 6:47
  • $\begingroup$ @OriGurel-Gurevich number of vertices is $n$ per color (so $2n$ is total number of vertices). I only look at bipartite graph genus. $\endgroup$
    – Turbo
    Commented Jul 23, 2017 at 6:50
  • $\begingroup$ @OriGurel-Gurevich sometimes max degree could be much larger than average degree. $\endgroup$
    – Turbo
    Commented Jul 23, 2017 at 6:50
  • $\begingroup$ Still, the conditions in 1 and 2 are equivalent, aren't they? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Jul 23, 2017 at 6:52

1 Answer 1

Reset to default
5
$\begingroup$

The answer is no. Hossein Namazi, Pekka Pankka, Juan Souto showed that expander graphs have genus that is linear in the number of vertices. You can construct bipartite, bounded degree expanders.

Improve this answer
$\endgroup$
2
  • $\begingroup$ bounded meaning degree $\leq 3$ possible? $\endgroup$
    – Turbo
    Commented Jul 23, 2017 at 8:20
  • $\begingroup$ Sure. A random 3-regular graph is an expander with high probability. If you want it to be bipartite, just replace every edge with a path of length 2. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Jul 23, 2017 at 15:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .