BASIS NUMBER AND PATHWIDTH

Babak Miraftab, Pat Morin, and Yelena Yuditsky · 2026

Read BASIS NUMBER AND PATHWIDTH by Babak Miraftab, Pat Morin, and Yelena Yuditsky (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-14095.txt.

Description

Babak Miraftab, Pat Morin, and Yelena Yuditsky link two measures of graph complexity in 2026. The basis number of a graph counts how edge cycles can be based on few sets. Pathwidth measures how close a graph is to a simple path in structure. The team proves two results relating the basis number to path decompositions.

Their first result shows the basis number is at most four times the pathwidth. A bound like this lets one measure stand in for an other. Graph measures guide algorithm design for networks, maps, and circuits. Firm links between them simplify many proofs.

Catalog record

CREATORBabak Miraftab, Pat Morin, and Yelena Yuditsky
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-14095

Browse the full library · About the Tower of Babel