  Consider a sequence of LexBFS vertex orderings {\sigma}1, {\sigma}2, . . .
where each ordering {\sigma}i is used to break ties for {\sigma}i+1. Since the
total number of vertex orderings of a finite graph is finite, this sequence
must end in a cycle of vertex orderings. The possible length of this cycle is
the main subject of this work. Intuitively, we prove for graphs with a known
notion of linearity (e.g., interval graphs with their interval representation
on the real line), this cycle cannot be too big, no matter which vertex
ordering we start with. More precisely, it was conjectured in [9] that for
cocomparability graphs, the size of this cycle is always 2, independent of the
starting order. Furthermore [27] asked whether for arbitrary graphs, the size
of such a cycle is always bounded by the asteroidal number of the graph. In
this work, while we answer this latter question negatively, we provide support
for the conjecture on cocomparability graphs by proving it for the subclass of
domino-free cocomparability graphs. This subclass contains cographs, proper
interval, interval, and cobipartite graphs. We also provide simpler independent
proofs for each of these cases which lead to stronger results on this
subclasses.
