Two Families of Graphs that are Not CCE-Orientable

Let \(D\) be a digraph. The competition-common enemy graph of \(D\) has the same set of vertices as \(D\) and an edge between vertices \(u\) and \(v\) if and only if there are vertices \(w\) and \(x\) in \(D\) such that \((w,u), (w,v), (u,x)\), and \((v,x)\) are arcs of \(D\). We call a graph a CCE-graph if it is the competition-common enemy graph of some digraph. We also call a graph \(G = (V, E)\) CCE-orientable if we can give an orientation \(F\) of \(G\) so that whenever \((w,u), (w,v), (u,x)\), and \((v,x)\) are in \(F\), either \((u,v)\) or \((v,u)\) is in \(F\). Bak \(et\; al. [1997]\) found a large class of graphs that are CCE-orientable and proposed an open question of finding graphs that are not CCE-orientable. In this paper, we answer their question by presenting two families of graphs that are not CCE-orientable. We also give a CCE-graph that is not CCE-orientable, which answers another question proposed by Bak \(et \;al. [1997]\). Finally, we find a new family of graphs that are CCE-orientable.