The LexCycle on $\overline{P_2\cup P_3}$-free Cocomparability Graphs

Abstract

A graph $G$ is a cocomparability graph if there exists an acyclic transitive orientation of the edges of its complement graph $\overline{G}$. LBFS${}^{+}$ is a variant of the generic Lexicographic Breadth First Search (LBFS), which uses a specific tie-breaking mechanism. Starting with some ordering ${\sigma }_0$ of $G$, let $\{{\sigma }_i{\}}_{i\ge 1}$ be the sequence of orderings such that ${\sigma }_i=$LBFS${}^{+}(G,{\sigma }_{i-1})$. The LexCycle($G$) is defined as the maximum length of a cycle of vertex orderings of $G$ obtained via such a sequence of LBFS${}^{+}$ sweeps. Dusart and Habib conjectured in 2017 that LexCycle($G$)=2 if $G$ is a cocomparability graph and proved it holds for interval graphs. In this paper, we show that LexCycle($G$)=2 if $G$ is a $\overline{P_2\cup P_3}$-free cocomparability graph, where a $\overline{P_2\cup P_3}$ is the graph whose complement is the disjoint union of $P_2$ and $P_3$. As corollaries, it's applicable for diamond-free cocomparability graphs, cocomparability graphs with girth at least 4, as well as interval graphs.

11 pages, 9 figures