The edge intersection graphs of paths in a tree
From MaRDI portal
Publication:792348
DOI10.1016/0095-8956(85)90088-7zbMath0537.05063OpenAlexW2017793597MaRDI QIDQ792348
Robert E. Jamison, Martin Charles Golumbic
Publication date: 1985
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(85)90088-7
Related Items
Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid, Graphs of edge-intersecting and non-splitting paths, Edge intersection graphs of \(L\)-shaped paths in grids, Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2, Coloring all directed paths in a symmetric tree, with an application to optical networks, An order theoretic framework for overlapping clustering, Complexity aspects of generalized Helly hypergraphs, Subtree filament graphs are subtree overlap graphs, Inverse chromatic number problems in interval and permutation graphs, What Is between Chordal and Weakly Chordal Graphs?, Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I, On the hereditary \((p,q)\)-Helly property of hypergraphs, cliques, and bicliques, Path covering problems and testing of printed circuits, Intersection graphs of vertex disjoint paths in a tree, On neighborhood-Helly graphs, Algorithmic aspects of intersection graphs and representation hypergraphs, Helly numbers of polyominoes, Colouring paths in directed symmetric trees with applications to WDM routing, Helly EPT graphs on bounded degree trees: characterization and recognition, Subpath acyclic digraphs, Minimum multiplicity edge coloring via orientation, Intersection graphs of orthodox paths in trees, Constant threshold intersection graphs of orthodox paths in trees, A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree, Clique-coloring UE and UEH graphs, Parameterized complexity of path set packing, On the generalized Helly property of hypergraphs, cliques, and bicliques, On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid, Path multicoloring in spider graphs with even color multiplicity, A Refined Analysis of Online Path Coloring in Trees, Revisiting Decomposition by Clique Separators, Representations of graphs and networks (coding, layouts and embeddings), On spectrum assignment in elastic optical tree-networks, Inapproximability and approximability of minimal tree routing and coloring, Path multicoloring with fewer colors in spiders and caterpillars, Characterization and recognition of generalized clique-Helly graphs, The \(k\)-edge intersection graphs of paths in a tree, Subtree and substar intersection numbers, Representing edge intersection graphs of paths on degree 4 trees, On edge-sets of bicliques in graphs, Towards a comprehensive theory of conflict-tolerance graphs, On the strong \(p\)-Helly property, On the complexity of recognizing directed path families, Constant tolerance intersection graphs of subtrees of a tree, Path problems in generalized stars, complete graphs, and brick wall graphs, The complexity of path coloring and call scheduling, Short length Menger's theorem and reliable optical routing, Optimal pricing of capacitated networks, Recognizing Helly edge-path-tree graphs and their clique graphs, Constraint Satisfaction with Counting Quantifiers, Edge intersection graphs of single bend paths on a grid, Dyadic representations of graphs, Fractional path coloring in bounded degree trees with applications, Equivalences and the complete hierarchy of intersection graphs of paths in a tree, Neighborhood subtree tolerance graphs, Single bend paths on a grid have strong helly number 4: errata atque emendationes ad “edge intersection graphs of single bend paths on a grid”, On superperfection of edge intersection graphs of paths, Intersection models of weakly chordal graphs, A superclass of edge-path-tree graphs with few cliques, Integrality properties of edge path tree families, Edge and vertex intersection of paths in a tree, Interval graphs and related topics, Triangulated edge intersection graphs of paths in a tree, Decomposition by clique separators, Strong cliques and equistability of EPT graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
- Edge and vertex intersection of paths in a tree
- Decomposition by clique separators
- The strong perfect graph conjecture for toroidal graphs
- The helly-type property of non-trivial intervals on a tree
- Partition numbers for trees and ordered sets
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- Information storage and retrieval - mathematical foundations. II: Combinatorial problems
- Critical perfect graphs and perfect 3-chromatic graphs
- A recognition algorithm for the intersection graphs of paths in trees
- Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture
- Intersection representations of graphs by arcs
- An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
- Coloring a Family of Circular Arcs
- Line perfect graphs
- The Strong Perfect Graph Conjecture for Planar Graphs
- A Theorem on Coloring the Lines of a Network
