Intersection graphs of paths in a tree
From MaRDI portal
Publication:1077439
DOI10.1016/0095-8956(86)90042-0zbMath0595.05062MaRDI 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
05C05: Trees
05A05: Permutations, words, matrices
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C99: Graph theory
Related Items
Coloring all directed paths in a symmetric tree, with an application to optical networks, Unnamed Item, Clique graphs and Helly graphs, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, Algorithmic aspects of intersection graphs and representation hypergraphs, Representations of graphs and networks (coding, layouts and embeddings), An algorithm for fraternal orientation of graphs, Counting clique trees and computing perfect elimination schemes in parallel, A note on the Hamiltonian circuit problem on directed path graphs, Recognizing clique graphs of directed and rooted path graphs, The forbidden subgraph characterization of directed vertex graphs, Recognition algorithm for intersection graphs of edge disjoint paths in a tree, Intersection graphs of concatenable subtrees of graphs, Completeness for intersection classes, Constant tolerance intersection graphs of subtrees of a tree, The separator theorem for rooted directed vertex graphs, Recognizing clique graphs of directed edge path graphs, Intersection graphs of vertex disjoint paths in a tree, Intersection graphs of Helly families of subtrees, Subpath acyclic digraphs, Modular intersection graphs, A faster algorithm to recognize undirected path graphs, Clique-coloring UE and UEH graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A slice genus lower bound from \(sl(n)\) Khovanov-Rozansky homology
- Edge and vertex intersection of paths in a tree
- Triangulated edge intersection graphs of paths in a tree
- Decomposition by clique separators
- An efficient PQ-graph algorithm for solving the graph-realization problem
- An algorithm for finding clique cut-sets
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- A recognition algorithm for the intersection graphs of paths in trees
- A characterisation of rigid circuit graphs
- Intersection representations of graphs by arcs
- Matrix characterizations of circular-arc graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- An algorithm for constructing edge-trees from hypergraphs
- The NP-Completeness of Edge-Coloring
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- A New Algorithm for Generating All the Maximal Independent Sets
- Line perfect graphs
- Incidence matrices with the consecutive 1’s property
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- A Characterization of Comparability Graphs and of Interval Graphs
