1987/03/01 by Reinhard Diestel · 5 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Characterization (materials science) #Chordal graph #Class (philosophy) #Combinatorics #Computer science #Discrete mathematics #Geometry #Graph #Graph Labeling and Dimension Problems #Indifference graph #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar #Planar graph #Property (philosophy) #Triangulation #graph theory and CDMA systems
paper · doi:10.1002/jgt.3190110108
published in Journal of Graph Theory 11(1), 43-52 (Wiley)
openalex publication_date 1987/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
Abstract Every planar triangulation G has the property that each induced cycle C of length at least 4 in G separates G , but no proper subgraph of C does. This property is trivially shared by all chordal graphs since these contain no such cycles at all. We ask to what extent maximally planar graphs and chordal graphs are unique with this property — or how much larger the class of graphs is that it determines. The answer is given in the form of a characterization of this class in terms of the simplicial decompositions of its elements. The theory of simplicial decompositions appears to be a very interesting, but still largely unexploited, method of characterization in graph theory, which seems tailor‐made for problems like the one discussed.