Score: 0

$K_{2,3}$-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two

Published: March 2, 2025 | arXiv ID: 2503.00798v1

By: Dibyayan Chakraborty

Potential Business Impact:

Makes complex networks simpler to understand.

Business Areas:
A/B Testing Data and Analytics

A graph $H$ is an induced minor of a graph $G$ if $H$ can be obtained from $G$ by a sequence of edge contractions and vertex deletions. Otherwise, $G$ is $H$-induced minor-free. In this paper, we prove that $K_{2,3}$-induced minor-free graphs admit a quasi-isometry with additive distortion to graphs with tree-width at most two. Our result implies that a recent conjecture of Nguyen et al. [Coarse tree-width (2025)] holds for $K_{2,3}$-induced minor-free graphs.

Page Count
16 pages

Category
Mathematics:
Combinatorics