10.23638/DMTCS-22-4-13
https://dmtcs.episciences.org/5385
Gao, Xiao-Lu
Xiao-Lu
Gao
Xu, Shou-Jun
Shou-Jun
Xu
The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs
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
episciences.org
Mathematics - Combinatorics
arXiv.org - Non-exclusive license to distribute
2020-12-09
2020-12-28
2020-12-28
eng
journal article
arXiv:1904.08076
10.48550/arXiv.1904.08076
1365-8050
10.48550/arxiv.1904.08076
https://dmtcs.episciences.org/5385/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
vol. 22 no. 4
Graph Theory
Researchers
Students