2-Competition Graphs
Garth Isaak, Suh-Ryung Kim, Terry A. McKees, Fred R. McMorris, Fred S. Roberts · SIAM Journal on Discrete Mathematics · 1992
If $D = ( V,A )$ is a digraph, its p-competition graph for p a positive integer has vertex set V and an edge between x and y if and only if there are distinct vertices $a_1, \cdots ,a_p $ in D with $( x,a_i )$ and $( y,a_i )$ arcs of D for each $i = 1, \cdots ,p$. This notion generalizes the notion of ordinary competition graph, which has been widely studied and is the special case where $p = 1$. Results about the case where $p = 2$ are obtained. In particular, the paper addresses the question of which complete bipartite graphs are 2-competition graphs. This problem is formulated as the following combinatorial problem: Given disjoint sets A and B such that $| A \cup B | = n$, when can one find n subsets of $A \cup B$ so that every a in A and b in B are together contained in at least two of the subsets and so that the intersection of every pair of subsets contains at most one element from A and at most one element from B?