×

Minimal reducible bounds for the class of \(k\)-degenerate graphs. (English) Zbl 0995.05073

Summary: Let \((\mathbb{L}^a,\subseteq)\) be the lattice of hereditary and additive properties of graphs. A reducible property \({\mathcal R}\in \mathbb{L}^a\) is called minimal reducible bound for a property \({\mathcal P}\in \mathbb{L}^a\) if in the interval \(({\mathcal P},{\mathcal R})\) of the lattice \(\mathbb{L}^a\), there are only irreducible properties. We prove that the set \({\mathbf B}({\mathcal D}_k)= \{{\mathcal D}_p\circ{\mathcal D}_q\mid k= p+ q+1\}\) is the covering set of minimal reducible bounds for the class \({\mathcal D}_k\) of all \(k\)-degenerate graphs.

MSC:

05C35 Extremal problems in graph theory
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI