A linear genus–girth bound for facial cycles
Let $\Sigma$ be a connected closed surface of genus $g \ge 1$: the orientable surface with $g$ handles or the nonorientable surface with $g$ crosscaps. Fix an integer $\ell \ge 3$ and consider finite simple graphs $G$ embedded on $\Sigma$ without crossings, of girth at least $\ell$, that are maximal for the embedding: adding any edge between two nonadjacent vertices of $G$ without crossings creates a cycle of length less than $\ell$. Embeddings need not be cellular. A facial cycle is a cycle of $G$ that forms the whole boundary of a face, a connected component of $\Sigma \setminus G$. Let $f_{\max}(\ell, \Sigma)$ be the largest length of a facial cycle of such a graph. Axenovich, Kießle, Sagdeev and Zhukovskii proved $$g(\ell - 5) \le f_{\max}(\ell, \Sigma) \le 24(2g + 1)\ell^2,$$ so that $f_{\max}(\ell, \Sigma)$ grows linearly in $g$ for each fixed $\ell \ge 6$. For the plane they proved $3\ell - 11 \le f_{\max} \le 8\ell - 13$ for $\ell \ge 7$, and Pálvölgyi and Zólomy independently showed that $f_{\max}$ is $O(\ell)$ there.
Problem. Is there an absolute constant $C$ such that every facial cycle of every such embedded graph has length at most $Cg\ell$? The same constant must work for both kinds of surface and for all $g \ge 1$ and $\ell \ge 3$.
Source: Axenovich, Kießle, Sagdeev and Zhukovskii (2026), Question 2.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- GT
- Keywords
- AIM Open Applied Problems, facial cycles, girth, graphs on surfaces
References
@article{axenovich2026,
author = {Axenovich, Maria and Kie{\ss}le, Leon and Sagdeev, Arsenii and Zhukovskii, Maksim},
title = {Faces in girth-saturated graphs on surfaces},
journal = {Discrete Comput. Geom.},
volume = {76},
number = {3},
year = {2026},
pages = {1503--1523},
doi = {10.1007/s00454-026-00833-x},
eprint = {2410.13481},
archivePrefix = {arXiv},
}
@misc{palvolgyi2025,
author = {P{\'a}lv{\"o}lgyi, D{\"o}m{\"o}t{\"o}r and Z{\'o}lomy, Krist{\'o}f},
title = {Stabbing non-piercing sets and face lengths in large girth plane graphs},
year = {2025},
eprint = {2504.10618},
archivePrefix = {arXiv},
}
@misc{aim-surface-girth-facial-linear-bound,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{A linear genus–girth bound for facial cycles}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/602-surface-girth-facial-linear-bound.md},
note = {Entry 602 at commit a153f46, 2026-10-13},
}
Resolution claims
Let $G$ be a finite simple graph of girth at least $\ell\ge3$, maximal in its fixed crossing-free embedding on an orientable surface with $g\ge1$ handles or a nonorientable surface with $g\ge1$ crosscaps. We prove that every simple cycle forming the entire boundary of a face has length at most $100000g\ell$. The same constant works for both surface types, including noncellular …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Open → Solution claimed | The registry's curators | A uniform linear bound for facial cycles on surfaces v1 recorded from AIM @ 24edaad, paper/manuscript.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00394, "A linear genus–girth bound for facial cycles", clopen.solutions.