Dense trees: a new look at degenerate graphs (Q849635): Difference between revisions

A \(k\)-dense forest (tree) is a (connected) graph of which each subgraph contains a vertex of degree at most \(k\). That is, the \(1\)-dense trees are exactly the trees, and all partial \(k\)-trees are \(k\)-dense forests, see \textit{H. L. Bodlaender} [Theor.\ Comput.\ Sci.\ 209, 1--45 (1998; Zbl 0912.68148)]. \(k\)-dense trees were studied in connection with first-fit colouring by \textit{G. Szekeres} and \textit{H. S. Wilf} [J.\ Comb.\ Theory 4, 1--3 (1967; Zbl 0171.44901)] and \textit{D. W. Matula} [SIAM Rev.\ 10, 481--482 (1968)], and also by \textit{D. R. Lick} and \textit{A. T. White} [Can.\ J.\ Math.\ 22, 1082--1096 (1970; Zbl 0202.23502)], who called them \(k\)-degenerate graphs, and by \textit{E. C. Freuder} [J.\ Assoc.\ Comput.\ Mach.\ 29, 24--32 (1982; Zbl 0477.68063)]. Here the focus is on maximal \(k\)-dense trees, their relation to \(k\)-trees, and the decomposition of \(k\)-dense trees into \(k\)-spanning trees.