Talk:Decomposition into forests and a bounded-degree subgraph

From Egres Open
Jump to: navigation, search

Spanning tree with lower degree bounds -- Tamás Király (talk) 15:51, 5 December 2014 (UTC)

The related question of finding a spanning tree with given lower degree bounds has been recently studied by Egawa and Ozeki in the papers Spanning trees with vertices having large degrees (author link, DOI link) and A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees (DOI link).

Re: Spanning tree with lower degree bounds -- Tamás Király (talk) 12:25, 21 May 2015 (UTC)

A simpler, algorithmic proof of the results of Egawa and Ozeki can be found in the the paper Spanning tree with lower bound on the degrees by Zoltán Király.