Tree-layout based graph classes: proper chordal graphs

DOI10.4230/LIPICS.STACS.2024.55MaRDI QIDQ6902665zbMATH OpenFDO

Authors Christophe Paul, Evangelos Protopapas

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2024.55

zbMATH Keywords

graph classesgraph isomorphismgraph representation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• O(M\cdot N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A Combinatorial Decomposition Theory
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• A survey of the algorithmic aspects of modular decomposition
• An optimal greedy heuristic to color interval graphs
• Complement reducible graphs
• Describing hereditary properties by forbidden circular orderings
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes
• Graph classes and forbidden patterns on three vertices
• Graph Classes: A Survey
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Graphs indecomposable with respect to the X-join
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonian circuits in interval graph generalizations
• scientific article; zbMATH DE number 3889566 (Why is no real title available?)
• scientific article; zbMATH DE number 3152801 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1820633 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Intersection graphs of non-crossing paths
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• On embedding graphs in trees
• On rigid circuit graphs
• On the computational complexity of ordered subgraph recognition
• Optimal greedy algorithms for indifference graphs
• Ordering without forbidden patterns
• Partitive hypergraphs
• Simultaneous FPQ-ordering and hybrid planarity testing
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The node-deletion problem for hereditary properties is NP-complete
• Transitiv orientierbare Graphen
• Tree-depth, subgraph coloring and homomorphism bounds
• Triangulated graphs and the elimination process
• Trivially perfect graphs

Cited in

(1)

• On the parameterized complexity of lineal topologies (depth-first spanning trees) with many or few leaves

This page was built for publication: Tree-layout based graph classes: proper chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902665)