Journal Article

The LexCycle on$\\overline{P_{2}\\cup P_{3}}$ -free Cocomparability Graphs

Gao, Xiao-Lu, Xu, Shou-Jun

2020

Overview

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

• Publisher: Discrete Mathematics & Theoretical Computer Science
• Subject: mathematics - combinatorics