Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2604.02646 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911564420874240 |
|---|---|
| author | Abe, Toshiki Furuya, Michitaka Mukae, Raiji Tsuchiya, Shoichi |
| author_facet | Abe, Toshiki Furuya, Michitaka Mukae, Raiji Tsuchiya, Shoichi |
| contents | In 2007, Ando and Egawa proved a theorem which provides a lower bound on the number of contractible edges preserving $4$-connectedness in $4$-connected graphs. In this paper, we refine their bounds, especially for the $4$-connected plane triangulations. In particular, we show that if $G$ is a $4$-connected plane triangulation of order at least $7$, then $G$ contains at least $|V_{\ge 5}|+2$ contractible edges preserving $4$-connectedness, where $V_{\ge 5}$ is the set of vertices of degree at least $5$. We also determine the extremal graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_02646 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the number of 4-contractible edges in plane triangulations Abe, Toshiki Furuya, Michitaka Mukae, Raiji Tsuchiya, Shoichi Combinatorics AMS 2020 Mathematics Subject Classification. 05C10, 05C40 In 2007, Ando and Egawa proved a theorem which provides a lower bound on the number of contractible edges preserving $4$-connectedness in $4$-connected graphs. In this paper, we refine their bounds, especially for the $4$-connected plane triangulations. In particular, we show that if $G$ is a $4$-connected plane triangulation of order at least $7$, then $G$ contains at least $|V_{\ge 5}|+2$ contractible edges preserving $4$-connectedness, where $V_{\ge 5}$ is the set of vertices of degree at least $5$. We also determine the extremal graphs. |
| title | On the number of 4-contractible edges in plane triangulations |
| topic | Combinatorics AMS 2020 Mathematics Subject Classification. 05C10, 05C40 |
| url | https://arxiv.org/abs/2604.02646 |