On a problem concerning tolerance graphs

DOI10.1016/0166-218X(93)90158-KMaRDI QIDQ689957zbMATH OpenFDO

Authors Thomas Andreae, Ulf Hennig, Andreas Parra

Publication date 16 January 1994

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(93)90158-K

zbMATH Keywords

bounded tolerance graph tolerance graph tree

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Review text

A tolerance graph is defined as an undirected graph \(G\) with the property that to each vertex \(x\) of \(G\) an interval \(I_ x\) on the real line and a positive number \(t_ x\) can be assigned in such a way that two vertices \(x\), \(y\) are adjacent in \(G\) if and only if the length of the interval \(I_ x \cap I_ y\) is greater than or equal to \(\min(t_ x,t_ y)\). If moreover \(t_ x\) is less than or equal to the length of \(I_ x\) for each vertex \(x\) of \(G\), then \(G\) is called a bounded tolerance graph. For a complement of a tree it is proved that it is a tolerance graph if and only if it is a bounded tolerance graph. This is a particular case of a conjecture by M. C. Golumbic, C. L. Monma and W. T. Trotter. Moreover, a complement of a tree being a tolerance graph is characterized by means of a forbidden subgraph.

Recommendations

Cites work

Cited in

(23)

This page was built for publication: On a problem concerning tolerance graphs

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