A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs

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.