Loading...
Please wait, while we are loading the content...
Similar Documents
The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Gao, Xiao-Lu Xu, Shou-Jun |
| Copyright Year | 2019 |
| Abstract | A graph $G$ is a cocomparability graph if there exists an acyclic transitive orientation of the edges of its complement graph $\overline{G}$. Starting at 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. It was conjectured by Dusart and Habib [Discrete Appl. Math., 216 (2017), pp. 149-161] that LexCycle$(G)$=2 if $G$ is a cocomparability graph. 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://arxiv.org/pdf/1904.08076v2.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
