Published in:
Discrete Applied Mathematics, Volume 242, 2018, Pages 82-88. DOI link
We concentrate on some recent results of Egawa and Ozeki \cite{EO,EO2}, and He
et al.\ \cite{He}.
We give shorter proofs and polynomial
algorithms as well.
We present two new proofs for the sufficient condition for having a spanning
tree with prescribed lower bounds on the degrees, achieved recently
by Egawa and Ozeki
\cite{EO}.
The first one is a natural proof using induction, and the second
one is a simple reduction to the theorem of Lovász \cite{L}.
Using an old algorithm
of Frank \cite{F} we show that the condition
of the theorem can be checked in time $O(m\sqrt{n})$, and moreover, in the same
running time -- if the condition is satisfied -- we can also generate the
spanning tree required. This gives the first polynomial algorithm for
this problem.
Next we show a nice application of this theorem for the simplest case of the
Weak Nine Dragon Tree Conjecture, and for
the game
coloring number of planar graphs,
first discovered by He et al. \cite{He}.
Finally we give a shorter proof and a polynomial
algorithm for a good characterization of having a spanning tree with
prescribed degree lower bounds, for the special case when $G[S]$ is a cograph,
where $S$ is the set of the vertices having degree lower bound prescription
at least two. This theorem was
proved by Egawa and Ozeki \cite{EO2} in 2014, they did not give a polynomial
algorithm.
Bibtex entry:
@techreport{egres-15-04,
AUTHOR | = | {Kir{\'a}ly, Zolt{\'a}n}, |
TITLE | = | {Spanning tree with lower bound on the degrees}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2015}, |
NUMBER | = | {TR-2015-04} |