A survey on pairwise compatibility graphs

DOI10.1016/J.AKCEJ.2019.12.011MaRDI QIDQ5012383zbMATH OpenOpenAlexFDO

Authors Md. Saidur Rahman, Shareef Ahmed

Publication date 1 September 2021

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.akcej.2019.12.011

zbMATH Keywords

leaf power graphsmulti-interval pairwise compatibility graphspairwise compatibility graphsphylogenetic trees

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90)

Recommendations

• Pairwise compatibility graphs: a survey
• Pairwise compatibility graphs
• Pairwise Compatibility Graphs
• Exploring pairwise compatibility graphs
• On graphs that are not PCGs

Cites work

• A decomposition theorem for partially ordered sets
• A necessary condition and a sufficient condition for pairwise compatibility graphs
• A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application
• Basic graph theory
• Characterizations of strongly chordal graphs
• Computing phylogenetic roots with bounded degrees and errors is NP-complete
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Exploring pairwise compatibility graphs
• Graph Classes: A Survey
• Graph Drawing
• Graphs that are not pairwise compatible: a new proof technique (extended abstract)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 2080275 (Why is no real title available?)
• Multi-interval pairwise compatibility graphs (extended abstract)
• On graph powers for leaf-labeled trees
• On graphs that are not PCGs
• On pairwise compatibility graphs having Dilworth number two
• On relaxing the constraints in pairwise compatibility graphs
• On the pairwise compatibility property of some superclasses of threshold graphs
• Pairwise compatibility graphs
• Pairwise compatibility graphs: a survey
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Rooted directed path graphs are leaf powers
• The complexity of satisfiability problems
• The Steiner problem in phylogeny is NP-complete
• Tolerance graphs
• Triangle-free outerplanar 3-graphs are pairwise compatibility graphs

Cited in

(16)

• Pairwise compatibility graphs
• A method for enumerating pairwise compatibility graphs with a given number of vertices
• New results on pairwise compatibility graphs
• Exact-2-relation graphs
• Pairwise compatibility graphs: complete characterization for wheels
• Multi-interval pairwise compatibility graphs (extended abstract)
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Pairwise compatibility graphs: a survey
• Discovering pairwise compatibility graphs
• Triangle-free outerplanar 3-graphs are pairwise compatibility graphs
• Pairwise Compatibility Graphs
• A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• On star-multi-interval pairwise compatibility graphs
• All graphs with at most 8 nodes are 2-interval-PCGs
• On generalizations of pairwise compatibility graphs

This page was built for publication: A survey on pairwise compatibility graphs

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