9
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ There have been numerous edits in a short span of time. Please be aware that every edit bumps the post to the top of the stack, and pushes off the front page other questions that are vying for attention. $\endgroup$ – Todd Trimble Jan 9 '20 at 1:34
  • $\begingroup$ @ToddTrimble Sorry I noticed some errors and then fiddled a lot with the formatting. Isn't there a stop gap which prevents bumps unless successive edits take a long enough time span? It would prevent this sort of problem for people obsessing over details. $\endgroup$ – Ethan Jan 9 '20 at 1:35
  • $\begingroup$ There's a 5-minute window for combining multiple edits into one. $\endgroup$ – Todd Trimble Jan 9 '20 at 1:39
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why is a circular orientation of a complete 3-partite graph Hamiltonian? You can try that with the 3 parts having size 1,2,1. $\endgroup$ – LeechLattice Jan 8 '20 at 14:11
  • $\begingroup$ Sorry I made an error, you are correct. The only part I don't understand, is how a connected graph $G$ with $\chi(G)=3$ that is not a complete tripartite graph, will not have a circular orientation. How would you prove this, say by contradiction somehow? I do not mean to sound ungrateful, but could you write me a short sketch/proof of this? I just don;'t understand why this is the case. $\endgroup$ – Ethan Jan 8 '20 at 14:32
  • $\begingroup$ The new edit may answer your question. $\endgroup$ – LeechLattice Jan 8 '20 at 14:40
  • $\begingroup$ What do you mean by $H$ is the smallest counter example? $H$ is a graph with the least number of vertices that is a counter example? Or edges? I'm confused with how you are describing connectivity between the color classes. I think what you're saying is that if $H$ is a graph with the least number of vertices serving as a counter example, then for any vertex $a\in V(H)$ the induced subgraph $G=H[V(H)\setminus\{a\}]$ must be a complete tripartite graph, and then from there you are somehow deriving that $H$ is a complete tripartite graph from $G$ which is a contradiction. Is this what you mean? $\endgroup$ – Ethan Jan 8 '20 at 14:50
  • $\begingroup$ Yes. "Smallest" means the graph with the least number of vertices, and the phase "$x$ is connected to $y$" means there is an edge $x → y$. $\endgroup$ – LeechLattice Jan 8 '20 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.