A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs
Md. Iqbal Hossain, Sammi Abida Salma, Md. Saidur Rahman, Debajyoti Mondal · Journal of Graph Algorithms and Applications · 2017
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.