On Generalizations of Pairwise Compatibility Graphs

A graph G is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree and an interval I, such that each leaf of the tree is a vertex of the graph, and there is an edge {x, y} in G if and only if the weight of the path in the tree connecting x and y lies within the interval I. Originating in phylogenetics, PCGs are closely connected to important graph classes like leaf-powers and multi-threshold graphs, widely applied in bioinformatics, especially in understanding evolutionary processes. In this paper we introduce two natural generalizations of the PCG class, namely k-OR-PCGs and k-AND-PCGs, which are the classes of graphs that can be expressed as union and intersection, respectively, of k PCGs. These classes can be also described using the concepts of the covering number and the intersection dimension of a graph in relation to the PCG class. We investigate how the classes of OR-PCG and AND-PCG are related to PCGs, k-interval-PCGs and other graph classes known in the literature. In particular, we provide upper bounds on the minimum k for which an arbitrary graph G belongs to k-interval-PCG, k-OR-PCG or k-AND-PCG classes. For particular graph classes we improve these general bounds. Moreover, we show that, for every integer k, there exists a bipartite graph that is not in the k-interval-PCG class, proving that there is no finite k for which the k-interval-PCG class contains all the graphs. This answers an open question of Ahmed and Rahman from 2017. Finally, using a Ramsey theory argument, we show that for any k, there exists graphs that are not in k-AND-PCG, and graphs that are not in k-OR-PCG.