The edge intersection graphs of paths in a tree
From MaRDI portal
We investigate the class of edge intersection graphs of a collection of paths in a tree (EPT graphs) where two paths edge intersect if they share an edge. The cliques of an EPT graph are characterized and shown to have strong Helly number 4. From this we demonstrate that one can find a maximum clique of an EPT graph in polynomial time. We show that the strong perfect graph conjecture holds for EPT graphs. Further complexity results follow from the observation that every line graph is an EPT graph. The class of EPT graphs is equivalent to the class of fundamental cycle graphs.
Recommendations
Cites work
- A recognition algorithm for the intersection graphs of paths in trees
- A Theorem on Coloring the Lines of a Network
- An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
- Coloring a Family of Circular Arcs
- Critical perfect graphs and perfect 3-chromatic graphs
- Decomposition by clique separators
- Edge and vertex intersection of paths in a tree
- scientific article; zbMATH DE number 3884202 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3910416 (Why is no real title available?)
- scientific article; zbMATH DE number 3757213 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3777537 (Why is no real title available?)
- scientific article; zbMATH DE number 3639680 (Why is no real title available?)
- Information storage and retrieval - mathematical foundations. II: Combinatorial problems
- Intersection representations of graphs by arcs
- Line perfect graphs
- Partition numbers for trees and ordered sets
- Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture
- The helly-type property of non-trivial intervals on a tree
- The Strong Perfect Graph Conjecture for Planar Graphs
- The strong perfect graph conjecture for toroidal graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- The validity of the strong perfect-graph conjecture for (K₄-e)-free graphs
Cited in
(78)- Equivalences and the complete hierarchy of intersection graphs of paths in a tree
- 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
- Algorithmic aspects of intersection graphs and representation hypergraphs
- Representations of graphs and networks (coding, layouts and embeddings)
- An order theoretic framework for overlapping clustering
- Minimum multiplicity edge coloring via orientation
- Path multicoloring in spider graphs with even color multiplicity
- On spectrum assignment in elastic optical tree-networks
- On edge-sets of bicliques in graphs
- Towards a comprehensive theory of conflict-tolerance graphs
- Constant tolerance intersection graphs of subtrees of a tree
- Dyadic representations of graphs
- Neighborhood subtree tolerance graphs
- Path covering problems and testing of printed circuits
- Intersection graphs of vertex disjoint paths in a tree
- Subpath acyclic digraphs
- On superperfection of edge intersection graphs of paths
- Constant threshold intersection graphs of orthodox paths in trees
- A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree
- Recognizing Helly edge-path-tree graphs and their clique graphs
- Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2
- Subtree filament graphs are subtree overlap graphs
- Helly EPT graphs on bounded degree trees: characterization and recognition
- Intersection graphs of orthodox paths in trees
- 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
- Representing edge intersection graphs of paths on degree 4 trees
- On the strong \(p\)-Helly property
- Path problems in generalized stars, complete graphs, and brick wall graphs
- Strong cliques and equistability of EPT graphs
- 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
- 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
- Graphs of edge-intersecting and non-splitting paths
- A refined analysis of online path coloring in trees
- Edge intersection graphs of \(L\)-shaped paths in grids
- Edge intersection graphs of single bend paths on a grid
- Inverse chromatic number problems in interval and permutation 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
- Edge and vertex intersection of paths in a graph
- On neighborhood-Helly graphs
- Clique-coloring UE and UEH graphs
- scientific article; zbMATH DE number 5763164 (Why is no real title available?)
- Helly numbers of polyominoes
- Coloring all directed paths in a symmetric tree, with an application to optical networks
- Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. II
- Colouring paths in directed symmetric trees with applications to WDM routing
- Revisiting decomposition by clique separators
- Optimal pricing of capacitated networks
- Strong pseudo transitivity and intersection graphs
- Constraint satisfaction with counting quantifiers
- What Is between Chordal and Weakly Chordal Graphs?
- Short length Menger's theorem and reliable optical routing
- Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
- The complexity of path coloring and call scheduling
- Fractional path coloring in bounded degree trees with applications
- Parameterized complexity of path set packing
- On non-superperfection of edge intersection graphs of paths
- Characterizations and clique coloring of edge intersection graphs on a triangular grid
- Subtree and substar intersection numbers
- Parameterized complexity of path set packing
- Edge intersection hypergraphs
- Helly and strong Helly numbers of B_k-EPG and B_k-VPG graphs
- Relationship among B₁-EPG, VPT and EPT graphs classes
- Clique coloring EPT graphs on bounded degree trees
- The undirected optical indices of trees
- Exact algorithms for edge deletion to Cactus
- Complexity aspects of generalized Helly hypergraphs
- Inapproximability and approximability of minimal tree routing and coloring
- On the complexity of recognizing directed path families
This page was built for publication: The edge intersection graphs of paths in a tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792348)
