A note on tolerance graph recognition
type: Item
instance of: scholarly article
title: A note on tolerance graph recognition
zbMATH Open document ID: 1062.05102
author: Ryan Hayward
author: Ron Shamir
published in: Discrete Applied Mathematics
publication date: 2004-11-23T00:00:00Z
review text: A graph \(G=(V,E)\) is a tolerance graph if there is a set \(I=\{I_v\mid v\in V\}\) of closed real intervals and a set \(\tau=\{\tau_v\mid v\in V\}\) of positive real numbers such that \((X,Y)\in E\) if and only if \(|I_x\cap I_y|\geq \min\{\tau_x,\tau_y\}\), see [\textit{M. C. Golumbic, C. L. Monma} and \textit{W. T. Trotter} jun., Discrete Appl. Math. 9, 157--170 (1984; Zbl 0547.05054)].
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 2118348
zbMATH Keywords: tolerance representation
zbMATH Keywords: class NP
reviewed by: Michael Hager
MaRDI profile type: Publication
full work available at URL: j.dam.2003.08.012
OpenAlex ID: W2169434358
cites work: Proper and unit tolerance graphs
cites work: Bipartite tolerance orders
cites work: Q4079613
cites work: Tolerance graphs, and orders
cites work: Q4198056
cites work: Q4949865
cites work: Q3322150
cites work: Tolerance graphs
cites work: Q5466018
cites work: Q4298260
cites work: Q3818127
cites work: Q3392273
DOI: 10.1016/J.DAM.2003.08.012
description: scientific article; zbMATH DE number 2118348