The LexCycle on P₂ P₃ -free cocomparability graphs

Abstract: A graph

G

is a cocomparability graph if there exists an acyclic transitive orientation of the edges of its complement graph

o v e r l i n e G

. LBFS

^{+}

is a variant of the generic Lexicographic Breadth First Search (LBFS), which uses a specific tie-breaking mechanism. Starting with some ordering

s i g m a_{0}

of

G

, let

{s i g m a_{i}}_{i g e q 1}

be the sequence of orderings such that

s i g m a_{i} =

LBFS

^{+} (G, s i g m a_{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

o v e r l i n e P_{2} c u p P_{3}

-free cocomparability graph, where a

o v e r l i n e P_{2} c u p 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.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: The LexCycle on \(\overline{P_2\cup P_3} \)-free cocomparability graphs