Maximum genus and girth of graphs (Q1297489): Difference between revisions

The maximum genus of a graph \(G\) is the largest \(k\) such that the graph has a cellular embedding of the orientable surface of genus \(k\). For simple graphs of minimum degree at least 3, the maximum genus always lies between \(\beta (G)/4\) and \(\beta (G)/2\), where \(\beta(G)\) is the cycle rank of \(G\). In this paper the author gives a lower bound on the maximum genus of a simple graph with girth \(g\) and minimum degree at least 3. If \(G\) is not the complete graph \(K_4\), then the maximum genus is at least \(\beta(G)(g-2)/(2g-2)+1/(g-1)\). The proof uses a relation between the maximum genus of \(G\) and the size of the largest independent set \(J\) with \(G-J\) connected.