episciences.org_5385_1675651286
1675651286
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
12
28
2020
vol. 22 no. 4
Graph Theory
The LexCycle on $\overline{P_{2}\cup P_{3}}$free Cocomparability Graphs
XiaoLu
Gao
ShouJun
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 tiebreaking 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_{i1})$. 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 diamondfree
cocomparability graphs, cocomparability graphs with girth at least 4, as well
as interval graphs.
12
28
2020
5385
https://arxiv.org/licenses/nonexclusivedistrib/1.0
arXiv:1904.08076
10.48550/arXiv.1904.08076
https://arxiv.org/abs/1904.08076v3
https://arxiv.org/abs/1904.08076v2
https://arxiv.org/abs/1904.08076v1
10.23638/DMTCS22413
https://dmtcs.episciences.org/5385

https://dmtcs.episciences.org/6994/pdf

https://dmtcs.episciences.org/6994/pdf