Intersection graphs of paths in a tree

DOI10.1016/0095-8956(86)90042-0zbMath0595.05062OpenAlexW1976489861MaRDI QIDQ1077439

Publication date: 1986

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(86)90042-0

zbMATH Keywords

intersection graph graphs perfect graphs chordal paths in a tree

Mathematics Subject Classification ID

Trees (05C05) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph theory (05C99)

Related Items

End simplicial vertices in path graphs, Intersection graphs of concatenable subtrees of graphs, A faster algorithm to recognize undirected path graphs, On models of directed path graphs non rooted directed path graphs, On basic chordal graphs and some of its subclasses, Coloring all directed paths in a symmetric tree, with an application to optical networks, Characterizing directed path graphs by forbidden asteroids, Path Problems in Complex Networks, Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage, Intersection graphs of vertex disjoint paths in a tree, Characterizing width two for variants of treewidth, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Algorithmic aspects of intersection graphs and representation hypergraphs, Intersection graphs of Helly families of subtrees, Helly EPT graphs on bounded degree trees: characterization and recognition, Subpath acyclic digraphs, Modular intersection graphs, Directed acyclic graphs with the unique dipath property, Truly non-trivial graphoidal graphs, Asteroidal quadruples in non rooted path graphs, A characterization of substar graphs, Two new characterizations of path graphs, Clique-coloring UE and UEH graphs, Succinct data structure for path graphs, Directed path graph isomorphism, Total coloring of rooted path graphs, The vertex leafage of chordal graphs, Decomposition by maxclique separators, On asteroidal sets in chordal graphs, On the correspondence between tree representations of chordal and dually chordal graphs, Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs, Characterization of 2-path signed network, Representations of graphs and networks (coding, layouts and embeddings), On spectrum assignment in elastic optical tree-networks, Counting independent sets in a tolerance graph, An algorithm for fraternal orientation of graphs, On the complexity of recognizing directed path families, Constant tolerance intersection graphs of subtrees of a tree, Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree, Counting maximal independent sets in directed path graphs, Intersection graphs of non-crossing paths, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Recognizing Helly edge-path-tree graphs and their clique graphs, A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs, From Path Graphs to Directed Path Graphs, Perfect graphs with polynomially computable kernels, Recognizing vertex intersection graphs of paths on bounded degree trees, Counting clique trees and computing perfect elimination schemes in parallel, A note on the Hamiltonian circuit problem on directed path graphs, Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction, The clique-separator graph for chordal graphs, Unnamed Item, A superclass of edge-path-tree graphs with few cliques, Path Partitions, Cycle Covers and Integer Decomposition, Recognizing clique graphs of directed and rooted path graphs, The forbidden subgraph characterization of directed vertex graphs, Completeness for intersection classes, Revising Johnson's table for the 21st century, The separator theorem for rooted directed vertex graphs, Clique graphs and Helly graphs, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, Recognizing clique graphs of directed edge path graphs, Computing the \(K\)-terminal reliability of directed path graphs, Recognition algorithm for intersection graphs of edge disjoint paths in a tree, Strong cliques and equistability of EPT graphs

Cites Work