Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-14T17:32:02.271Z Has data issue: false hasContentIssue false

k-Degenerate Graphs

Published online by Cambridge University Press:  20 November 2018

Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Graphs possessing a certain property are often characterized in terms of a type of configuration or subgraph which they cannot possess. For example, a graph is totally disconnected (or, has chromatic number one) if and only if it contains no lines; a graph is a forest (or, has point-arboricity one) if and only if it contains no cycles. Chartrand, Geller, and Hedetniemi [2] defined a graph to have property Pn if it contains no subgraph homeomorphic from the complete graph K n+1 or the complete bipartite graph

For the first four natural numbers n, the graphs with property Pn are exactly the totally disconnected graphs, forests, outerplanar and planar graphs, respectively. This unification suggested the extension of many results known to hold for one of the above four classes of graphs to one or more of the remaining classes.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1970