Path degeneracy and applications

In this work, we relate girth and path-degeneracy in classes with sub-exponential expansion, with explicit bounds for classes with polynomial expansion and proper minor-closed classes that are tight up to a constant factor (and tight up to second order terms if a classical conjecture on existence of $g$-cages is verified). As an application, we derive bounds on the generalized acyclic indices, on the generalized arboricities, and on the weak coloring numbers of high-girth graphs in such classes. Along the way, we prove a conjecture proposed in [T.~Bartnicki et al., Generalized arboricity of graphs with large girth, Discrete Mathematics 342 (2019), no.~5, 1343--1350.], which asserts that, for every integer $k$, there is an integer $g(p,k)$ such that every $K_k$ minor-free graph with girth at least $g(p,k)$ has $p$-arboricity at most $p+1$.

Publication Details

Journal
ArXiv.org
Published
2025-03-24
Primary Topic
Graph theory and applications
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Path degeneracy and applications

ArXiv.org
Graph theory and applications
article

Path degeneracy and applications

article en

Abstract

In this work, we relate girth and path-degeneracy in classes with sub-exponential expansion, with explicit bounds for classes with polynomial expansion and proper minor-closed classes that are tight up to a constant factor (and tight up to second order terms if a classical conjecture on existence of $g$-cages is verified). As an application, we derive bounds on the generalized acyclic indices, on the generalized arboricities, and on the weak coloring numbers of high-girth graphs in such classes. Along the way, we prove a conjecture proposed in [T.~Bartnicki et al., Generalized arboricity of graphs with large girth, Discrete Mathematics 342 (2019), no.~5, 1343--1350.], which asserts that, for every integer $k$, there is an integer $g(p,k)$ such that every $K_k$ minor-free graph with girth at least $g(p,k)$ has $p$-arboricity at most $p+1$.

ArXiv.org
Openalex Percentile: Top 41%
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Path degeneracy and applications · ArXiv.org (2025) | TGRS Research Map | TGRS