General results on tolerance intersection graphs
Let \(\mu\) be a function that assigns to each subset \(S\) of a set \(X\) a positive real number \(\mu(S)\), and let \(V\) be a finite set and \(S_ i\) a subset of \(X\) for all \(v_ i\in V\). Then a tolerance function assigns to each \(S_ i\) a positive real number \(t_ i\). Furthermore let \(\Phi\) be a function that assigns a positive real number to each pair of positive reals. By applying both these functions \(\mu\) and \(\Phi\) Jacobson, McMorris and Mulder defined: A finite graph \(G=(V,E)\) is a \(\Phi\)- tolerance intersection graph iff every vertex \(v_ i\in V\) can be assigned a set \(S_ i\) and a tolerance \(t_ i\) so that \(v_ iv_ j\in E\) iff \(\mu(S_ i\cap S_ j)\geq\Phi(t_ i,t_ j)\). In the special case where \(\Phi\) is the constant function \(p\) and \(\mu\) is the size of the set \(S_ i\), \(G\) is called a \(p\)-intersection graph. (In the case that every \(v_ i\) is assigned an interval \(J_ i\) and \(\mu(J_ i)\) is the length of this interval, \(G\) is called a \(\Phi\)- tolerance interval graph.) In the present paper are stated the following general results about such graphs: Every graph is a \(\Phi\)-tolerance intersection graph for any \(\Phi\) (Proposition 1), and this also means that every graph is a \(p\)- intersection graph for any \(p\). All trees are \(\Phi\)-tolerance interval graphs for monotone increasing functions \(\Phi\) (Theorem 3). Almost all graphs are not \(\Phi\)-tolerance interval graphs for any polynomial function \(\Phi\) (Theorem 4). A generalization of results from Erdős- Goodman-Posa which are related to the so-called \(p\)-intersection number of \(G\) and which are given by an inequality depending on \(p\) and the number \(n\) of vertices (Proposition 2).
- The \(p\)-intersection number of a complete bipartite graph and orthogonal double coverings of a clique
- On k-weak orders: Recognition and a tolerance result
- Intuitionistic fuzzy tolerance graphs with application
- Fuzzy \(\phi\)-tolerance competition graphs
- Towards a comprehensive theory of conflict-tolerance graphs
- Neighborhood subtree tolerance graphs
- Tolerance competition graphs
- \(p\)-competition graphs
- A note on tolerance graph recognition
- Proper and unit tolerance graphs
- Any complete preference structure without circuit admits an interval representation
- Characterizations of fuzzy interval graphs
- Tolerance intersection graphs on binary trees with constant tolerance 3
- Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2
- A sufficient condition for boundedness of tolerance graphs
- scientific article; zbMATH DE number 1156625 (Why is no real title available?)
- Archimedean ϕ ‐tolerance graphs
- scientific article; zbMATH DE number 867635 (Why is no real title available?)
- Rank‐tolerance graph classes
- On self-graphoidal graphs and their complements
- -threshold and -tolerance chain graphs
- On a problem concerning tolerance graphs
- p-competition numbers
- Forbidden induced subgraphs for bounded p-intersection number
This page was built for publication: General results on tolerance intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3984466)