Given a $k$-partite graph $G$ formed from the union of a set of $k$-cliques, is $G$ a comparability graph?

Question

Are all $k$-partite graphs with a pure clique complex of dimension $k-1$ transitively orientable?

A transitive orientation is as assignment of a direction to each edge in $G$ such that if $v \rightarrow w$ and $w \rightarrow x$ are in the graph, then $v \rightarrow x$ is too. Any graph with such an orientation is called a comparability graph

Edit: Does it make a difference if $k$ is even?

Answer 1

Given a $k$-partite graph which is the union of $k$-cliques, is there an orientation such that whenever $u \to v$ and $v \to w$ are edges, $u \to w$ is an edge?

The answer is no. For example, take the tripartite graph with tripartition $$\{a_1,a_2,a_3\} \cup \{b_1, b_2, b_3\} \cup \{c_1, c_2, c_3\}$$ which is the union of four triangles: the triangles with vertices $$\{a_1,b_1,c_1\} \quad \{a_2,b_2,c_2\} \quad \{a_3,b_3,c_3\} \quad \{a_1, b_2, c_3\}.$$ Here's why. The three parts are symmetric, so without loss of generality, we can assume that we orient the last triangle as $a_1 \to b_2, a_1 \to c_3, b_2 \to c_3$. Then there are two cases:

• If edge $a_2b_2$ is oriented $a_2 \to b_2$, then we have edges $a_2 \to b_2$ and $b_2 \to c_3$, but can't have the edge $a_2 \to c_3$ (because $a_2c_3$ is not an edge of the original graph).
• If edge $a_2b_2$ is oriented $b_2 \to a_2$, then we have edges $a_1 \to b_2$ and $b_2 \to a_2$, but can't have the edge $a_1 \to a_2$ (because $a_1a_2$ is not an edge of the original graph).

So this graph does not have a transitive orientation.

---

The same construction generalizes to all $k>2$: starting with $k^2$ vertices $\{ v_{ij} : 1 \le i,j \le k\}$, we take the $k$ cliques on sets $\{v_{i1}, \dots, v_{ik}\}$, and the "diagonal" clique $\{v_{11}, v_{22}, \dots, v_{kk}\}$.

No matter how we orient the diagonal clique, there will be some vertex $v_{ii}$ that's neither the source nor the sink of that orientation. In that case, any way to orient the clique $\{v_{i1}, v_{i2}, \dots, v_{in}\}$ will give us a failure of transitivity: a directed path of the form $v_{hh} \to v_{ii} \to v_{ij}$ or $v_{ij} \to v_{ii} \to v_{hh}$ with no edge to complete it.

(For that matter, this $k$-partite graph has the tripartite graph from earlier as an induced subgraph, which immediately tells us that it's also a counterexample.)

For $k=2$, of course, any bipartite graph which is the union of edges (that is, any bipartite graph) has a transitive orientation, where we orient all the edges to point from one part to the other.