@article{BHHM23spanningtreesubdivisions,
title={Spanning trees of smallest maximum degree in subdivisions of graphs},
author={Brause, Christoph and Harant, Jochen and H{\"o}rsch, Florian and Mohr, Samuel},
note = {submitted. },
archivePrefix = {arXiv},
eprint={2210.04669},
biburl = {http://samuel-mohr.de/files/bib/23.bib},
abstract = {Given a graph {$G$} and a positive integer {$k$}, we study the question whether {$G^\star$} has a spanning tree of maximum degree at most {$k$} where {$G^\star$} is the graph that is obtained from {$G$} by subdividing every edge once. Using matroid intersection, we obtain a polynomial algorithm for this problem and a characterization of its positive instances. We use this characterization to show that {$G^\star$} has a spanning tree of bounded maximum degree if {$G$} is contained in some particular graph class. We study the class of 3-connected graphs which are embeddable in a fixed surface and the class of {$(p-1)$}-connected {$K_p$}-minor-free graphs for a fixed integer {$p$}. We also give tightness examples for most of these classes. }
}