On generalizations of pairwise compatibility graphs

DOI10.46298/DMTCS.12295MaRDI QIDQ6986991zbMATH OpenFDO

Authors Tiziana Calamoneri, Manuel Lafond, Angelo Monti, Blerina Sinaimeri

Publication date 7 May 2025

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Copyright license arXiv.org Non-exclusive license to distribute

Full work available at URL https://doi.org/10.46298/DMTCS.12295

zbMATH Keywords

covering numberintersection dimensionmulti-interval-PCGpairwise compatibility graphs

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory (05C90)

Cites work

• L(3, 2, 1)-labeling of certain planar graphs
• A method for enumerating pairwise compatibility graphs with a given number of vertices
• A necessary condition and a sufficient condition for pairwise compatibility graphs
• A note on 1-planar graphs
• A survey on pairwise compatibility graphs
• Better bounds for poset dimension and boxicity
• Complement reducible graphs
• Covering planar graphs with forests
• Decompositions of graphs into trees, forests, and regular subgraphs
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Edge-Disjoint Spanning Trees of Finite Graphs
• Exact-2-relation graphs
• Exploring pairwise compatibility graphs
• Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
• Generalized Fitch graphs. III: Symmetrized Fitch maps and sets of symmetric binary relations that are explained by unrooted edge-labeled trees
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Inferring phylogenetic trees from the knowledge of rare evolutionary events
• Intersection dimensions of graph classes
• Interval representations of planar graphs
• Leaf Powers and Their Properties: Using the Trees
• Multi-interval pairwise compatibility graphs (extended abstract)
• Multithreshold graphs
• On a class of posets and the corresponding comparability graphs
• On graph powers for leaf-labeled trees
• On graphs that are not PCGs
• On relaxing the constraints in pairwise compatibility graphs
• On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions
• Orthology relations, symbolic ultrametrics, and cographs
• Pairwise compatibility graphs: a survey
• Parallel recognition of series-parallel graphs
• Parameterized leaf power recognition via embedding into graph products
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Recognizing k-leaf powers in polynomial time, for constant k
• Some classes of graphs that are not PCGs
• Some recent results on Ramsey-type numbers
• Some results on linear arboricity
• Some results on multithreshold graphs
• The theory of regular graphs
• Three ways to cover a graph
• Triangle-free outerplanar 3-graphs are pairwise compatibility graphs
• Über eine Eigenschaft der ebenen Komplexe

This page was built for publication: On generalizations of pairwise compatibility graphs

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