Metraipolis › archive › dc_ced1f04af45e

Bicoloured-interval and interval-sandwich graphs: two new classes in the tolerance hierarchy — arXiv:2609.12293

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12293
License (as archived)
CC0-1.0
Archived
2026-10-16T03:49:15.808Z
SHA-256 of the archived text
9d6d70d28fcbba4d0770531c9ee9f509508119d75eb61dec812603bdaa38b5bf
Stable URL of this page
https://metraipolis.com/documento/dc_ced1f04af45e

How to cite

Bicoloured-interval and interval-sandwich graphs: two new classes in the tolerance hierarchy — arXiv:2609.12293 — arXiv (en), https://arxiv.org/abs/2609.12293 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ced1f04af45e (Metraipolis archive dc_ced1f04af45e, sha256 9d6d70d28fcbba4d0770531c9ee9f509508119d75eb61dec812603bdaa38b5bf)
BibTeX
@misc{dcced1f04af45e,
  title = {Bicoloured-interval and interval-sandwich graphs: two new classes in the tolerance hierarchy — arXiv:2609.12293},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12293},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ced1f04af45e; sha256 9d6d70d28fcbba4d0770531c9ee9f509508119d75eb61dec812603bdaa38b5bf},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12293. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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~$\textsf{NP}$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-14 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.12293 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:18:59.204Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).