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

Abstract

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.