Subgraphs with restricted degrees of their vertices in polyhedral maps on compact 2-manifolds (Q1600806)

The paper deals with structural properties of polyhedral maps on a compact 2-manifold \(M\), extending to the case of Euler characteristic \(\chi (M)<0\) known results about the 2-sphere, the torus, the projective plane and the Klein bottle (see \textit{I. Fabrici} and \textit{S. Jendrol'} [Discrete Math. 191, No. 1-3, 83-90 (1998; Zbl 0956.05059)] and the authors [Eur. J. Comb. 20, No. 8, 821-832 (1999; Zbl 0942.05018)]). If \(\mathcal H(k, M)\) denotes the family of all polyhedral maps of order at least \(k\) on \(M\), let \(\tau(k,M)\) be the minimum integer such that any map \(G \in \mathcal H(k, M)\) contains a connected subgraph \(H\) of order \(k\) for which \(\deg_G(A)\leq \mathcal H(k, M)\) holds for every vertex \(A\) of \(H\). The main result of the paper states that, if \(\chi (M)<0\), then for every \(k \geq 4\) the following realtion holds: \[ \left \lfloor \frac{2k+2}{3} \right \rfloor \left( \left \lfloor \frac{5 + \sqrt{49-24\chi(M)}}{2}\right \rfloor - \frac 3 2\right)\leq \tau(k,M)\leq\left \lfloor (k+1) \frac{5 + \sqrt{49-24\chi(M)}}{3}\right \rfloor. \] Moreover, the authors prove the existence of infinitely many orientable as well as infinitely many nonorientable surfaces, such that the above upper bound results are tight for every \(k \equiv 2 \pmod 3\).