A Survey of Maximal k-Degenerate Graphs and k-Trees

Abstract

This article surveys results on maximal $k$-degenerate graphs, $k$-trees, and related classes including simple $k$-trees, $k$-paths, maximal outerplanar graphs, and Apollonian networks. These graphs are important in many problems in graph theory and computer science. Types of results surveyed include structural characterizations, enumeration, degree sets and sequences, chromatic polynomials, algorithms, and related extremal problems.

Keywords

• k-tree
• maximal k-degenerate graph
• simple k-tree
• k-path
• outerplanar graph
• apollonian network