1970/10/01 by Don R. Lick, Arthur T. White · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #Mathematics #Combinatorics #Arboricity #Cograph #Discrete mathematics #1-planar graph #Pathwidth #Graph product #Dense graph #Graph #Line graph #Planar graph
paper · pdf · doi:10.4153/cjm-1970-125-1
openalex publication_date 1970/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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 P n 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 P n 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.