Pairwise Compatibility Graphs of Unweighted Caterpillars
Abstract
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 interval. Using this characterization, we derive structural properties of the class, including bounded twin-width, and study its relation with familiar graph families. We show that the class contains cycles and two-dimensional grids, while it excludes natural obstructions such as the subdivided star S2,2,2,2,2, the cube graph Q3, the wheel W6, and the complement of the $3$-sunlet. We also consider restricted representations, including centipede witnesses and representations with a given interval and we give a polynomial-time recognition algorithm when the interval is fixed.
Related
- Additive mappings of unweighted directed graphs preserving individual values of the cycle length
- Deep Reinforcement Learning on Item-Compatibility Graphs for One-Dimensional Bin Packing
- Improvement of the dimension bound for unweighted RCD spaces
- Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games
- Total {k}-domination in caterpillars: Structural properties and exact results
BibTeX
@misc{antony2026pairwise,
title = {{Pairwise Compatibility Graphs of Unweighted Caterpillars}},
author = {Cyriac Antony and Manuel Lafond and Angelo Monti and Blerina Sinaimeri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14681},
eprint = {2610.14681},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14681},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Pairwise Compatibility Graphs of Unweighted Caterpillars
AU - Cyriac Antony
AU - Manuel Lafond
AU - Angelo Monti
AU - Blerina Sinaimeri
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14681
UR - https://arxiv.org/abs/2610.14681
AB - 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 interval. Using this characterization, we derive structural properties of the class, including bounded twin-width, and study its relation with familiar graph families. We show that the class contains cycles and two-dimensional grids, while it excludes natural obstructions such as the subdivided star S_2,2,2,2,2, the cube graph Q_3, the wheel W_6, and the complement of the $3$-sunlet. We also consider restricted representations, including centipede witnesses and representations with a given interval and we give a polynomial-time recognition algorithm when the interval is fixed.
ER -