Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016)
DOI: 10.7155/jgaa.00419
A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
Vol. 21, no. 3, pp. 341-352, 2017. Regular paper.
Abstract In this paper we give a necessary condition and a sufficient condition for a graph to be a pairwise compatibility graph (PCG). Let $G$ be a graph and let $G^c$ be the complement of $G$. We show that if $G^c$ has two disjoint chordless cycles then $G$ is not a PCG. On the other hand, if $G^c$ has no cycle then $G$ is a PCG. Our conditions are the first necessary condition and the first sufficient condition for pairwise compatibility graphs in general. We also show that there exist some graphs in the gap of the two conditions which are not PCGs.
Submitted: May 2016.
Reviewed: November 2016.
Revised: December 2016.
Accepted: December 2016.
Final: January 2017.
Published: February 2017.
Communicated by Mohammed Kaykobad and Rossella Petreschi
article (PDF)
BibTeX