Linear time recognition of P4-indifference graphs

This paper shows how a linear time algorithm for the P 4 -indifference graphs recognition can be designed. This algorithm strongly relies on modular decomposition as a preprocessing. But linear time modular decomposition algorithms are still complicated to program. So the natural question is: can this preprocessing step be avoided ? So it has been shown that prime P 4 -indifference graphs are interval graphs. It is well known that Lexicographic Breadth First Search (Lex-BFS) [RTL76] plays an important role on interval graphs [HM91, COS98, HMPV97]. The order Lex-BFS visits the vertices of the input graph can be seen as the output of Lex-BFS: a Lex-BFS ordering. For example in [COS98], 4 sweeps of particular Lex-BFS are used to compute a characteristic ordering of interval graphs (the i-th sweep starts on the last visited vertex of the previous sweep). One can wonder if Lex-BFS can be used to compute a P 4 -indifference ordering. As illustrated by the graph of figure 4, the answer is n