On interval-families, transitive orientations and Gallai arc-equivalence in graphs.

Authors: P. Bertrand (1) and P. Duchet (2)

(1) ENST-Bretagne, TAMCIC/IASC, Technopole Brest-Iroise, BP 832, 29285 BREST Cedex, France
(2) Univ. Paris 6, Equipe Combinatoire, Case 189, 4 place Jussieu, 75252 PARIS
Cedex 05, France


Let 'G' be any undirected graph. We define a 'K'-filament as a subset 'F' of a clique 'K', such that for each 'x' in 'K - F', all arcs 'xy' with 'y' in 'F' are equivalent, in the sense of the transitive closure of the Gamma relation defined by Gallai in his characterization of comparability graphs. When 'G' is a comparability graph, the set 'F[K]' of all 'K'-filaments Consists of those subsets of 'K' which are intervals of each transitive orientation of 'G'. In addition, the set 'Lin(F[K])' of all linear orders 'L' on 'K' such that each 'K'-filament is an interval of 'L', coincides with the set of restrictions to 'K' of all transitive orientations of 'G'. It follows that there exist some pairwise disjoint maximal cliques, say 'K1', ... , 'Kp', such that the set of transitive orientations of 'G' is in bijection with the cartesian product of sets 'Lin(F[Ki])' for 'i = 1, ... , p'. Furthermore, a set-system, say '(X, S)', is the collection of 'X'-filaments of a clique 'X' in some graph 'G' iff 'S' is a partitive set family. In this case, the tree decomposition of 'S' coincides with the trace on 'X' of the Gallai modular decomposition of 'G'. Finally, in case of 'C5'-free graphs that satisfy some injectivity condition concerning the map 'x --> N(x)', the recognition of comparability graphs can be reduced to the problem of deciding if there exists some linear order for which a specific family of clique-filaments is a collection of intervals. This last result generalizes a characterization obtained by Moore for 2-dimensional posets of height 2.