Xiao-Lu Gao ; Shou-Jun Xu - The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs

dmtcs:5385 - Discrete Mathematics & Theoretical Computer Science, December 28, 2020, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-13
The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability GraphsArticle

Authors: Xiao-Lu Gao ; Shou-Jun Xu

    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.


    Volume: vol. 22 no. 4
    Section: Graph Theory
    Published on: December 28, 2020
    Accepted on: December 9, 2020
    Submitted on: April 18, 2019
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 354 times.
    This article's PDF has been downloaded 169 times.