On Critical Graphs for Opsut’s Conjecture

Abstract

A graph $G=(V(G),E(G))$ is the competition graph of an acyclic digraph $D=(V(D),A(D))$ if $V(G)=V(D)$ and there is an edge in $G$ between vertices $x,y\in V(G)$ if and only if there is some $v\in V(D)$ such that $xv,yv\in A(D)$. The competition number $k(G)$ of a graph $G$ is the minimum number of isolated vertices needed to add to $G$ to obtain a competition graph of an acyclic digraph. Opsut conjectured in 1982 that if $\theta (N(v))\le 2$ for all $v\in V(G)$, then the competition number $k(G)$ of $G$ is at most $2$, with equality if and only if $\theta (N(v))=2$ for all $v\in V(G)$. (Here, $\theta (H)$ is the smallest number of cliques covering the vertices of $H$.) Though Opsut (1982) proved that the conjecture is true for line graphs and recently Kim and Roberts (1989) proved a variant of it, the original conjecture is still open. In this paper, we introduce a class of so-called critical graphs. We reduce the question of settling Opsut’s conjecture to the study of critical graphs by proving that Opsut’s conjecture is true for all graphs which are disjoint unions of connected non-critical graphs. All $K_4$-free critical graphs are characterized. It is proved that Opsut’s conjecture is true for critical graphs which are $K_4$-free or are $K_4$-free after contracting vertices of the same closed neighborhood. Some structural properties of critical graphs are discussed.