Tolerance competition graphs (Q1805304)

The \(\phi\)-tolerance competition graph of a digraph is a generalization of the \(p\)-competition graph defined by Kim, McKee, McMorris, and Roberts (see the previous review [\textit{S. R. Kim}, \textit{T. A. McKee}, the second author and \textit{F. S. Roberts}, \(p\)-competition graphs, Linear Algebra Appl. 217, 167-178 (1995; Zbl 0824.05027)]) which conforms the idea of a general tolerance intersection graph [\textit{M. S. Jacobson}, the second author and \textit{H. M. Mulder}, Introduction to tolerance intersection graphs, in: Graph theory, combinatorics and applications, Vol. 2, 705-723 (1991) and \textit{M. S. Jacobson}, the second author and \textit{E. R. Scheinerman}, General results on tolerance intersection graphs, J. Graph Theory 15, No. 6, 573-577 (1991; Zbl 0741.05070)]. A graph \(G= (V, E)\) is a \(\phi\)-tolerance competition graph if there is a digraph \(D= (V, A)\), an assignment of non-negative integers to the vertices \(v_ i\mapsto t_ i\) and a symmetric integer function \(\phi\) such that for \(i\neq j\), \(v_ i v_ j\in E\) if the out-neighbourhoods of \(v_ i\) and \(v_ j\) have at least \(\phi(t_ i, t_ j)\) vertices in common. If \(\phi= p\) identically, then \(G\) is a \(p\)-competition graph. The authors give a general characterization of \(\phi\)-tolerance competition graphs and specific results when \(\phi\) is the minimum, maximum, or sum function.