{"id":"arxiv/2610.14681","url":"https://arxiv.org/abs/2610.14681","tags":["cs.DM","math.CO"],"score":0,"title":"Pairwise Compatibility Graphs of Unweighted Caterpillars","domain":"cs.DM","source":"arxiv","authors":["Cyriac Antony","Manuel Lafond","Angelo Monti","Blerina Sinaimeri"],"reviews":0,"subject":"cs.DM","summary":"In this paper we study pairwise compatibility graphs whose witness tree is required to be an unweighted caterpillar. This is a natural restriction of PCGs, in the same line of research as the study of star witnesses, which led to the class of double-threshold graphs. In the caterpillar case, we show that this restriction is equivalent to a one-dimensional difference-labelling problem: a graph admits such a representation if and only if its vertices can be assigned integer labels so that adjacency is determined exactly by whether the absolute difference of two labels belongs to a given…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-10","reactions":{}}