Proper and unit bitolerance orders and graphs

DOI10.1016/S0012-365X(97)00043-5MaRDI QIDQ1381846zbMATH OpenOpenAlexFDO

Authors Kenneth P. Bogart, Garth Isaak

Publication date 31 August 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(97)00043-5

zbMATH Keywords

Fishburn representation interval order tolerance order unit

Mathematics Subject Classification ID

Graph theory (05C99) Partial orders, general (06A06)

Review text

An order \(\prec\) is a tolerance order on a set of vertices if one may assign to each vertex \(x\) an interval \(I_x\) of real numbers and a real number \(t_x\) called a tolerance in such a way that \(x\prec y\) if and only if the overlap of \(I_x\) and \(I_y\) is less than the minimum of \(t_x\) and \(t_y\) and the center of \(I_x\) is less than the center of \(I_y\). An order is a bitolerance order if and only if there are intervals \(I_x\) and real numbers \(t_l(x)\) and \(t_r(x)\) assigned to the vertex \(x\) in such a way that \(x\prec y\) if and only if the overlap of \(I_x\) and \(I_y\) is less than both \(t_r(x)\) and \(t_l(y)\) and the center of \(I_x\) is less than the center of \(I_y\). A tolerance or bitolerance order is said to be bounded if no tolerance is larger than the length of the corresponding interval. A bounded tolerance graph or bitolerance graph is the incomparability graph of a bounded tolerance order or bitolerance order. Such a graph or order is called proper if it has a representation using intervals no one of which is a proper subset of another, and it is called unit if it has a representation using only unit intervals. The authors prove that a bitolerance graph or order is proper if and only if it is a unit.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Proper and unit bitolerance orders and graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1381846)