A class of graphs each tolerance graph of which is a bounded one (Q1341250)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A class of graphs each tolerance graph of which is a bounded one |
scientific article |
Statements
A class of graphs each tolerance graph of which is a bounded one (English)
0 references
24 January 1995
0 references
\textit{M. C. Golumbic}, \textit{C. L. Monma} and \textit{W. T. Trotter} [Discrete Appl. Math. 9, 157-170 (1984; Zbl 0547.05054)] conjectured that if \(G\) is a comparability graph then its complement \(H\) is a tolerance graph iff \(H\) is a bounded tolerance graph. Here the author proves this conjecture for a class of graphs which contains all bipartite graphs.
0 references
interval graph
0 references
comparability graph
0 references
tolerance graph
0 references
