Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420309 | Discrete Applied Mathematics | 2006 | 7 Pages |
Abstract
We prove that a triangle-free graph G is a tolerance graph if and only if there exists a set of consecutively ordered stars that partition the edges of G. Since tolerance graphs are weakly chordal, a tolerance graph is bipartite if and only if it is triangle-free. We, therefore, characterize those tolerance graphs that are also bipartite. We use this result to show that in general, the class of interval bigraphs properly contains tolerance graphs that are triangle-free (and hence bipartite).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Arthur H. Busch,