Near-perfect matchings in highly connected 1-planar graphs with a local crossing constraint
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.05267
curl -X POST /api/v1/records/arxiv/2602.05267/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.05267/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'