2025/03/12 by Thérèse Biedl, Biedl, Therese
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2503.09440
openalex publication_date 2025/03/12 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28
In his Ph.D. thesis, Farber proved that every strongly chordal graph can be represented as intersection graph of subtrees of a weighted tree, and these subtrees are ``compatible''. Moreover, this is an equivalent characterization of strongly chordal graphs. To my knowledge, Farber never published his results in a conference or a journal, and the thesis is not available electronically. As a service to the community, I therefore reproduce the proof here. I then answer some questions that naturally arise from the proof. In particular, the sufficiency proof works by showing the existence of a simple vertex. I give here an alternate sufficiency proof that directly converts a set of compatible subtrees into a strong elimination order.