The elimination procedure for the competition number (Q2713639)

The competition graph of an acyclic digraph \(D\) is the undirected graph \(G\) with \(V(G)=V(D)\) and with two vertices \(x,y\) being adjacent if and only if both \((x,a)\) and \((y,a)\) are arcs of \(D\) for some vertex \(a\). Every graph \(G\) becomes a competition graph by adding some isolated vertices. The minimum number of such vertices is called the competition number of \(G\) and is denoted by \(k(G)\). The authors present an elimination procedure that gives an upper bound on \(k(G)\) and, for a large class of graphs, the exact value of \(k(G)\). The procedure is a modification of the procedure introduced by the second author in [Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642, 477-490 (1978; Zbl 0389.90036)].