Archimedean ϕ ‐tolerance graphs

Let ϕ be a symmetric binary function, positive valued on positive arguments. A graph G = ( V , E ) is a ϕ‐ tolerance graph if each vertex υ ∈ V can be assigned a closed interval I υ and a positive tolerance t υ so that xy ∈ E ⇔ | I x ∩ I y |≥ ϕ ( t x , t y ). An Archimedean function has the property of tending to infinity whenever one of its arguments tends to infinity. Generalizing a known result of [15] for trees, we prove that every graph in a large class (which includes all chordless suns and cacti and the complete bipartite graphs K 2, k ) is a ϕ‐tolerance graph for all Archimedean functions ϕ. This property does not hold for most graphs. Next, we present the result that every graph G can be represented as a ϕ G ‐tolerance graph for some Archimedean polynomial ϕ G . Finally, we prove that there is a „universal” Archimedean function ϕ * such that every graph G is a ϕ * ‐tolerance graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 179–194, 2002