The elimination procedure for the competition number is not optimal (Q2499585): Difference between revisions

A graph \(G=(V,E)\) is the competition graph of an acyclic digraph \(D=(V,A)\) (called food web) if \(E = \{\{x,y\} \mid \exists z \in V ((x,z) \in A \wedge (y,z) \in A)\}\). The competition number of \(G\) is the minimum \(r\) such that \(G+rK_1\) is a competition graph, see \textit{R. J. Opsut} [SIAM J.\ Algebraic Discrete Methods 3, 420--428 (1982; Zbl 0512.05032)]. As the title states, the elimination procedure introduced by \textit{S.-R. Kim} and \textit{F. S. Roberts} [Ars Comb.\ 50, 97--113 (1998; Zbl 0963.05071)] provides only an upper bound on the competition number.