When does a graph have a circular orientation? Or equivalently can anyone help me characterize this particular class of $3$-colorable perfect graphs?

Question

Call an oriented digraph $D=(V,A)$ circular when for all $\small x,y,z\in V$ if $(x,y)\in A$ and $(y,z)\in A$ then $(z,x)\in A$ or equivalently if $D$ is any oriented digraph whose arc set is a circular relation.

With that said, when does an undirected graph have a circular orientation?

---

I can prove these graphs are perfect i.e. graphs with circular orientations have identical clique and chromatic numbers for all their induced subgraphs, also I can show they are $3$-colorable and there exists a family of forbidden induced subgraphs which characterizes them. Its also easy to see these graphs look similar in their definition to comparability graphs i.e. graphs which have an orientation $D=(V,A)$ such that for all $x,y,z\in V$ if $(x,y)\in A$ and $(y,z)\in A$ then $(x,z)\in A$ (this last arc in the definition of circular orientations is flipped) also like graphs with circular orientations, these (graphs with transitive orientations) are similarly perfect graphs. Now Gallai proved the countable set $S$ below, of forbidden induced subgraph isomorphism types characterized every comparability graph:

$$\small S=\{(G_k)^{\complement}:1\leq k\leq 8\}\cup\{B_1^{\complement},B_2^{\complement}\}\cup\bigcup_{n=2}^{\infty}\{C_{2n+1},J_n,J'_{n+1},J''_n,(K_n)^{\complement},(C_{n+4})^{\complement},(L_{n-1})^{\complement},(L'_{n-1})^{\complement}\}$$

Where the indexed types $G,B,K,L,C,J,J',J''$ are each defined diagrammatically as follows:

Thus surely characterizing those graphs with circular orientations by a family of forbidden induced subgraphs can not be harder then this? I mean they have bounded clique/chromatic number so I'd expect them not to be that complicated, not like the above graph types. Perhaps even looking for a forbidden induced subgraph characterization is overkill, though there must be some simple way to characterize these graphs, if fifty years ago Tibor Gallai managed to do this for the class of far more complicated, comparability graphs. Right? If so I'd appreciate any help.

Answer 1

The class is exactly the class of bipartite graphs ∪ complete 3-partite graphs.

Such a graph must be paw-free. To check this, note that the orientation of the triangle in the paw must be cyclic, and check the two cases where the remaining edge points to or away from the triangle.

According to ISGCI, a graph both paw-free and perfect is a bipartite graph or a complete multipartite graph.

As such graphs have chromatic number≤3, they are bipartite graphs or complete 3-partite graphs. And it's easy to check that these two types of graphs are circularly orientable.

EDIT: There's a proof that a 3-partite circularly orientable graph is complete.

Proof. It's easy to check the case where the graph have 3 vertices. Suppose $H$ is the smallest counterexample. As $H$ is 3-partite, call the three color classes $A$, $B$ and $C$. Without loss of generality, assume $A$ has more that 2 vertices and $a$ is a vertex of $A$, and every vertex of $A\backslash a$ is connected to every vertex of $B$, and that holds for $B$ to $C$ and $C$ to $A\backslash a$.

Since the graph is connected, $a$ is connected either to some vertex in $B$ or some vertex in $C$. If $a$ is connected to some vertex in $C$, then by circularity, every vertex in $A\backslash a$ is connected to $a$, which is a contradiction. So $a$ is connected to some vertex in $B$. By circulatity, every vertex in $C$ is connected to $a$, and by the same reasoning, $a$ is connected to every vertex in $B$. Thus $H$ is complete, and is not a counterexample.

So there are no counterexamples, which proves the claim.