Near-perfect matchings in highly connected 1-planar graphs with a local crossing constraint
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915775882723328 |
|---|---|
| author | Ouyang, Licheng Zhang Yuanqiu Huang Zhangdong |
| author_facet | Ouyang, Licheng Zhang Yuanqiu Huang Zhangdong |
| contents | For planar graphs, it is well known that high connectivity implies a Hamiltonian cycle and hence any 4-connected planar graph has a near-perfect matching. Nevertheless, whether 6-connected 1-planar graphs admit near-perfect matchings remains largely open. The prior art established this for 4-connected 1-planar graphs only when each crossing involves four endpoints that induce a $K_4$. In this paper, we study 6-connected 1-planar graphs that are drawn such that at all crossings the four endpoints induce a 4-cycle (plus perhaps more edges). We show that these have a near-perfect matching, and in fact even stronger, their scattering number is at most one. Moreover, under the local crossing restriction, the requirement of 6-connectivity is best possible; this is witnessed by explicit constructions due to Biedl and Fabrici et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_05267 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Near-perfect matchings in highly connected 1-planar graphs with a local crossing constraint Ouyang, Licheng Zhang Yuanqiu Huang Zhangdong Combinatorics For planar graphs, it is well known that high connectivity implies a Hamiltonian cycle and hence any 4-connected planar graph has a near-perfect matching. Nevertheless, whether 6-connected 1-planar graphs admit near-perfect matchings remains largely open. The prior art established this for 4-connected 1-planar graphs only when each crossing involves four endpoints that induce a $K_4$. In this paper, we study 6-connected 1-planar graphs that are drawn such that at all crossings the four endpoints induce a 4-cycle (plus perhaps more edges). We show that these have a near-perfect matching, and in fact even stronger, their scattering number is at most one. Moreover, under the local crossing restriction, the requirement of 6-connectivity is best possible; this is witnessed by explicit constructions due to Biedl and Fabrici et al. |
| title | Near-perfect matchings in highly connected 1-planar graphs with a local crossing constraint |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.05267 |