On a problem concerning tolerance graphs

Link:
Autor/in:
Erscheinungsjahr:
1993
Medientyp:
Text
Schlagworte:
  • Article
  • Article
Beschreibung:
  • We consider tolerance graphs as defined by Golumbic, Monma, and Trotter (1984). These authors proposed a conjecture which can be stated as follows: If H is a comparability graph, then its complement is a tolerance graph if and only if it is a bounded tolerance graph. A result which supports this conjecture was obtained by one of us in his Diploma-Thesis (Hennig, 1988) where it was shown that, for a tree T, the following three conditions are equivalent: (i) is a tolerance graph, (ii) is a bounded tolerance graph, (iii) T does not contain T3 as a subtree, where T3 denotes the tree which consists of three paths of length 3 starting at a common vertex. It is the purpose of the present note to give a short proof of this result.
Lizenz:
  • info:eu-repo/semantics/openAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/6d1f3da9-4480-46e7-93ba-4694415cf47c