{"docId":6994,"paperId":5385,"url":"https:\/\/dmtcs.episciences.org\/5385","doi":"10.23638\/DMTCS-22-4-13","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":410,"name":"vol. 22 no. 4"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"arXiv","repositoryIdentifier":"1904.08076","repositoryVersion":5,"repositoryLink":"https:\/\/arxiv.org\/abs\/1904.08076v5","dateSubmitted":"2019-04-18 11:53:49","dateAccepted":"2020-12-09 22:55:47","datePublished":"2020-12-28 10:08:45","titles":["The LexCycle on $\\overline{P_{2}\\cup P_{3}}$-free Cocomparability Graphs"],"authors":["Gao, Xiao-Lu","Xu, Shou-Jun"],"abstracts":["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\\geq 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.","Comment: 11 pages, 9 figures"],"keywords":["Mathematics - Combinatorics"]}