Intersection graphs of concatenable subtrees of graphs

DOI10.1016/0166-218X(94)90081-7zbMath0805.05068OpenAlexW2000918288MaRDI QIDQ1331898

Jorge Urrutia, Fanica Gavril

Publication date: 26 January 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90081-7

zbMATH Keywords

intersection graphcliquepolynomial time algorithmsHelly familydirected cyclesrooted subtreefraternal orientationacanthusconcatenable subtreesdirected subtree

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Intersection graphs of proper subtrees of unicyclic graphs, 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs, Finding intersection models: from chordal to Helly circular-arc graphs, Intersection representations of matrices by subtrees and unicycles on graphs, \(1\)-perfectly orientable graphs and graph products, Normal fraternally orientable graphs satisfy the strong perfect graph conjecture, Partial Characterizations of 1‐Perfectly Orientable Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Intersection graphs of paths in a tree
• An algorithm for fraternal orientation of graphs
• Triangulated graphs and the elimination process
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• An Efficient Test for Circular-Arc Graphs
• Algorithms on circular-arc graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph