Two-\(\phi\)-tolerance competition graphs (Q1917307)

A graph \(G= G(V, E)\) is a \(\phi\)-tolerance competition graph if there is a directed graph \(D= D(V, A)\) such that each vertex \(v_i\in V\) can be assigned a nonnegative integer \(t_i\) such that, for \(i\neq j\), \(v_i v_j\in E(G)\) iff \(|O(v_i)\cap O(v_j)|\geq \phi(t_i, t_j)\), where \(O(v)\) is the set of out-neighbors of \(v\) and where \(\phi\) is a symmetric function from \(\mathbb{N}\times \mathbb{N}\) into \(\mathbb{N}\). The not necessarily distinct integers \(t_i\) are called tolerances. In the present paper two-\(\phi\)-tolerance competition graphs are considered, these graphs are \(\phi\)-tolerance competition graphs in which the tolerances are selected from a set \(\{p, q\}\), and therefore such graphs are also designated as \(\{p, q\}\)-\(\phi\)-tolerance competition graphs. Further, the function \(\phi\) is restricted to the natural functions minimum (min), maximum (max), and sum. In Section 2 the case \(p= 0\) is treated and characterizations depending on an invariant which is called the \(q\)-edge clique cover number of \(G\) are given for \(\{0, q\}\)-min-tolerance competition graphs and for \(\{0, q\}\)-max-tolerance competition graphs (Theorems 1 and 3). For example, from Theorem 1 follows the special case (Theorem 2): Let \(G\) be a graph of order \(n\), let \(M\) be the set of its vertices of degree \(n- 1\), and suppose \(G- M\) has no isolated vertices. Then \(G\) is a \(\{0, q\}\)-min-tolerance competition graph iff \(G\) is a \(q\)-competition graph. By Theorem 4 a simple characterization of a \(\{0, 1\}\)-max-tolerance competition graph is given and from this follows that \(K_{2, 3}\) is such a graph (Corollary 2). Theorem 5 contains a characterization of a \(\{0, q\}\)-sum-tolerance competition graph. In Section 3 the tolerances are restricted to \(\{0, 1\}\). Let \(m\) be the class of \(\{0, 1\}\)-min-tolerance competition graphs and \(m'\) the class of graphs which are not \(\{0, 1\}\)-min-tolerance competition graphs. The classes \(M\) and \(M'\) for the case \(\phi=\max\), and \(S\) and \(S'\) for the case \(\phi=\text{sum}\), are similarly defined. By the help of examples of graphs the authors show that the intersection of any two of these six classes (where the two are not \(m\) and \(m'\), \(M\) and \(M'\), or \(S\) and \(S'\)) are nonempty, with exception of \(m\cap S'\). This is an open problem. Finally, in Section 4, a general result is given for the case \(\phi=\text{max}\) (Theorems 6 and 7).