A note on perfectly orderable graphs

NEW

Problem: Reconstructed statement: for finite simple graphs, with “$H$-free” meaning no induced copy of $H$, if $G_1,G_2$ are both $P_4$-free and $2K_2$-free on a common vertex set $V$, then $G=(V,E(G_1)\cup E(G_2))$ is perfectly orderable. Equivalently, $G$ has a vertex order with no induced path $a b c d$ satisfying $a<b$ and $d<c$. This is the standard Chvátal definition used in the paper’s context.

Result: The conjecture is true.

Let $G=G_1\cup G_2$. First, $G$ has no induced cycle of length at least $5$. Indeed, let $C$ be such a hole. In a fixed $G_i$, two disjoint edges of $C$ cannot both occur: if no third edge among their four endpoints occurs, they induce a $2K_2$; if a third edge occurs, it must be the intervening cycle edge, giving three consecutive edges of $C$, which induce a $P_4$, since $C$ has no chords in $G$. Hence the cycle-edges of $C$ contained in each $G_i$ are pairwise intersecting, so at most two. Two graphs cannot cover a cycle of length at least $5$, contradiction.

Now suppose $G$ had an induced antihole $\overline{C_k}$, $k\ge5$, on vertex set $S$. Put $H_i=\overline{G_i[S]}$. Since $G_i[S]$ is $P_4,2K_2$-free, $H_i$ is $P_4,C_4$-free, hence trivially perfect. Also

$$H_1\cap H_2=\overline{G_1[S]\cup G_2[S]}=C_k.$$

But no $C_k$, $k\ge5$, is the edge-intersection of two trivially perfect graphs.

Proof of that fact: represent each connected trivially perfect graph as the comparability graph of a rooted tree. For each vertex $v$ of the cycle, its two cycle-neighbors are nonadjacent in $C_k$, so in at least one of the two rooted trees they are incomparable; then $v$ must be their common ancestor in that tree. Adjacent vertices cannot have this property in the same tree, so the witnesses alternate. Thus $k=2m$, $m\ge3$. Let $O,E$ be the alternating vertex classes, witnessed by trees $T_1,T_2$, respectively.

In $T_1$, consecutive vertices of $O$ are comparable, so the induced subgraph on $O$ is connected trivially perfect; it has a vertex $a\in O$ ancestral to all of $O$. Then $a$ is comparable in $T_1$ with every vertex, hence in $T_2$ it is comparable with exactly its two cycle-neighboring vertices $f,g\in E$. The connected trivially perfect graph on $E$ in $T_2$ has an ancestral root; this root must be one of $f,g$, say $f$. Thus $f$ is universal in $H_2$. Repeating the same argument on $O\setminus\{a\}$ shows that the other $O$-neighbor $b$ of $f$ is ancestral to all $O\setminus\{a\}$, hence universal in $H_1$. Similarly, in $E\setminus\{f\}$, the vertex $g$ is ancestral to all remaining $E$-vertices. Let $h\ne f$ be the other $E$-neighbor of $b$. Since $m\ge3$, $h\ne g$. But $g$ is ancestral to $h$ in $T_2$, and $h$ is ancestral to $b$, so $g$ is comparable with $b$ in $T_2$. Since $b$ is universal in $H_1$, $bg\in H_1\cap H_2=C_k$, contradicting that $b$ and $g$ are not adjacent on the cycle.

Therefore $G$ has no holes or antiholes of length at least $5$, so $G$ is weakly chordal. By the standard theorem that every weakly chordal graph is perfectly orderable, $G$ is perfectly orderable.

Degenerate cases cause no exception: graphs with fewer than five vertices are automatically weakly chordal, and if $G_1,G_2$ originally have different vertex sets, adding isolated vertices gives a common vertex set without changing the hypotheses or union.

Citation: Uses the standard theorem that weakly chordal graphs are perfectly orderable; see R. B. Hayward, “Weakly triangulated graphs,” J. Combin. Theory Ser. B 39 (1985), 200–208, and Chvátal’s characterization of perfect orders in V. Chvátal, “Perfectly ordered graphs,” Ann. Discrete Math. 21 (1984), 63–65.