Two local and one global properties of 3-connected graphs on compact 2-dimensional manifolds (Q707019)

Let \({\mathcal{G}}(\mathbb{M})\) be the family of all 3-connected graphs that can be embedded in a compact 2-manifold \(\mathbb{M}\) with Euler characteristic \(\chi(\mathbb{M}) < 0\). The authors prove that each graph \(G \in {\mathcal{G}}(\mathbb{M})\) that contains a \(k\)-vertex path, \(k \geq 4\), contains also a \(k\)-vertex path \(P_k\) such that each of its vertices has in \(G\) degree at most \(2 + \lfloor (6k-6-2\varepsilon)(1 + \frac{| \chi(\mathbb{M})| }{3}) \rfloor\) (where \(\varepsilon = 0\) for \(k\) even and \(\varepsilon = 1\) for \(k\) odd), and that each graph \(G \in {\mathcal{G}}(\mathbb{M})\) on at least \(k \geq 5\) vertices contains a connected subgraph of order \(k\) such that each of its vertices has in \(G\) degree at most \(2 +\lfloor (4k-2)(1 + \frac{| \chi(\mathbb{M})| }{3})\rfloor \). Both bounds are best possible; in addition, there are also the best bounds for smaller values of \(k\) provided. As an application of these results, it is proved that every graph \(G \in {\mathcal{G}}(\mathbb{M})\) has a 2-connected spanning subgraph \(H\) such that \(\Delta(H) \leq 20 - 6\chi(\mathbb{M})\).