# Is bipartite graph genus bound by $O(\mbox{max deg})$?

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.$)

• What is n? is it the coloring number of the graph? – Ori Gurel-Gurevich Jul 23 '17 at 6:46
• 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. – Ori Gurel-Gurevich Jul 23 '17 at 6:47
• @OriGurel-Gurevich number of vertices is $n$ per color (so $2n$ is total number of vertices). I only look at bipartite graph genus. – Turbo Jul 23 '17 at 6:50
• @OriGurel-Gurevich sometimes max degree could be much larger than average degree. – Turbo Jul 23 '17 at 6:50
• Still, the conditions in 1 and 2 are equivalent, aren't they? – Ori Gurel-Gurevich Jul 23 '17 at 6:52

• bounded meaning degree $\leq 3$ possible? – Turbo Jul 23 '17 at 8:20