Follow

Killing a vortex: arxiv.org/abs/2207.04923, by Thilikos and Wiederrecht.

Robertson and Seymour's structural decomposition of minor-closed graph families glues together surface-embedded graphs, a few arbitrarily-connected "apex" vertices, and "vortices", bounded-pathwidth graphs attached to faces. For graph matching, vortices are problematic. This new preprint describes the families that don't need them and shows that they are exactly the ones whose matchings can be counted quickly.

· · Web · 0 · 0 · 0
Sign in to participate in the conversation
Mathstodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!