Bicoloured-interval and interval-sandwich graphs: two new classes in the tolerance hierarchy
Abstract
We introduce two new graph classes, the bicoloured-interval graphs and the interval-sandwich graphs, arising from the study of the robust line fitting problem in computer vision. In a bicoloured-interval graph, each vertex is assigned a real interval and one of two colours. Vertices of different colours are adjacent precisely when their intervals intersect, and vertices of the same colour precisely when the centre of one interval lies in the other. Discarding the colouring yields the interval-sandwich graphs, sandwiched between the 50%-tolerance graph and the intersection graph of a family of intervals. We prove structural results for both classes, determining which holes, antiholes, trees, and complete bipartite graphs each contains. Consequently, neither class is characterised by finitely many forbidden induced subgraphs. We place both classes strictly between the unit tolerance graphs and the co-comparability graphs in the tolerance hierarchy, separating them from the neighbouring classes. In particular, we construct an infinite family of proper tolerance graphs, each of which is a minimal forbidden induced subgraph for the bicoloured-interval graphs. Finally, we consider the recognition problems for both classes. We show that every graph in either class has a polynomial-size integer representation, and hence that both problems lie in~textsfNP.
Related
- A sandwich theorem for the spectrum of graph coverings
- Sprinkling for random regular graphs and Kim-Vu's sandwich conjecture
- Sandwich Variance Estimation in Scale Mixture of Skew-Normal Linear Mixed Models.
- Sandwich Slice: Optimal Transport Potentials Are Optimal Generalized Slicers
- Sharp Sobolev Sandwich and Approximation Rates of Radon-Domain Lp Ridge Integral Spaces for ReLUk Networks
BibTeX
@misc{basit2026bicolouredinterval,
title = {{Bicoloured-interval and interval-sandwich graphs: two new classes in the tolerance hierarchy}},
author = {Abdul Basit and David Suter and Erchuan Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.12293},
eprint = {2609.12293},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12293},
}
RIS
TY - UNPB
TI - Bicoloured-interval and interval-sandwich graphs: two new classes in the tolerance hierarchy
AU - Abdul Basit
AU - David Suter
AU - Erchuan Zhang
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.12293
UR - https://arxiv.org/abs/2609.12293
AB - We introduce two new graph classes, the bicoloured-interval graphs and the interval-sandwich graphs, arising from the study of the robust line fitting problem in computer vision. In a bicoloured-interval graph, each vertex is assigned a real interval and one of two colours. Vertices of different colours are adjacent precisely when their intervals intersect, and vertices of the same colour precisely when the centre of one interval lies in the other. Discarding the colouring yields the interval-sandwich graphs, sandwiched between the 50%-tolerance graph and the intersection graph of a family of intervals. We prove structural results for both classes, determining which holes, antiholes, trees, and complete bipartite graphs each contains. Consequently, neither class is characterised by finitely many forbidden induced subgraphs. We place both classes strictly between the unit tolerance graphs and the co-comparability graphs in the tolerance hierarchy, separating them from the neighbouring classes. In particular, we construct an infinite family of proper tolerance graphs, each of which is a minimal forbidden induced subgraph for the bicoloured-interval graphs. Finally, we consider the recognition problems for both classes. We show that every graph in either class has a polynomial-size integer representation, and hence that both problems lie in~textsfNP.
ER -