Intersection graphs of non-crossing paths
DOI10.1016/J.DISC.2023.113498zbMATH Open1515.05152OpenAlexW2955374454MaRDI QIDQ6041577FDOQ6041577
Authors: Steven Chaplick 
Publication date: 31 May 2023
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2023.113498
Recommendations
Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)
Cites Work
- Topics in Intersection Graph Theory
- Computing a minimum outer-connected dominating set for the class of chordal graphs
- Finding Hamiltonian circuits in proper interval graphs
- Clustering and domination in perfect graphs
- Intersection graphs of paths in a tree
- Claw-free graphs---a survey
- Which problems have strongly exponential complexity?
- Algorithmic graph theory and perfect graphs
- Incidence matrices and interval graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Representation of a finite graph by a set of intervals on the real line
- Characterizing path graphs by forbidden induced subgraphs
- Representations of chordal graphs as subtrees of a tree
- Characterizations of strongly chordal graphs
- HAMILTONian circuits in chordal bipartite graphs
- On domination and independent domination numbers of a graph
- Algorithmic Aspects of Vertex Elimination on Graphs
- Title not available (Why is that?)
- Computing role assignments of proper interval graphs in polynomial time
- The forbidden subgraph characterization of directed vertex graphs
- From path graphs to directed path graphs
- Edge Dominating Sets in Graphs
- The clique-separator graph for chordal graphs
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- A recognition algorithm for the intersection graphs of paths in trees
- Intersection graphs of Helly families of subtrees
- Finding and counting small induced subgraphs efficiently
- Dominating Sets in Chordal Graphs
- Clique tree generalization and new subclasses of chordal graphs
- Steiner trees, connected domination and strongly chordal graphs
- Sphere and dot product representations of graphs
- Title not available (Why is that?)
- The LBFS structure and recognition of interval graphs
- Independent domination in chordal graphs
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- The edge Hamiltonian path problem is NP-complete for bipartite graphs
- A characterisation of rigid circuit graphs
- On the complexity of fixed parameter clique and dominating set
- A faster algorithm to recognize undirected path graphs
- A note on the Hamiltonian circuit problem on directed path graphs
- On nontransitive indifference
- Boundary classes for graph problems involving non-local properties
- Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
- Finding four-node subgraphs in triangle time
- Intersection graphs of non-crossing paths
- Combinatorial problems on \(H\)-graphs
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- On the tractability of optimization problems on \(H\)-graphs
- On \(H\)-topological intersection graphs
- Title not available (Why is that?)
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
Cited In (2)
This page was built for publication: Intersection graphs of non-crossing paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041577)
