2025/03/24 by Lin, Y., de Mendez, P. Ossona
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.18614
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 Kk minor-free graph with girth at least g(p,k) has p-arboricity at most p+1.