Clique Graphs of Chordal and Path Graphs
From MaRDI portal
Publication:4296528
DOI10.1137/S0895480191223191zbMath0798.05046WikidataQ56430111 ScholiaQ56430111MaRDI QIDQ4296528
Claudson F. Bornstein, Jayme Luiz Szwarcfiter
Publication date: 19 June 1994
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
treeintersection graphcharacterizationspanning treepolynomial algorithmclique graphpath graphchordal graphexpanded tree
Trees (05C05) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph theory (05C99)
Related Items
\(r\)-dominating cliques in graphs with hypertree structure ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ Split clique graph complexity ⋮ Dually chordal graphs ⋮ Characterization of classical graph classes by weighted clique graphs ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ On minimal vertex separators of dually chordal graphs: properties and characterizations ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ NP-completeness results for edge modification problems ⋮ The complexity of clique graph recognition ⋮ Cube intersection concepts in median graphs ⋮ Split Clique Graph Complexity ⋮ The clique operator on cographs and serial graphs ⋮ Recognizing clique graphs of directed and rooted path graphs ⋮ Recognizing clique graphs of directed edge path graphs ⋮ Intersection graphs of maximal hypercubes