We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in and hence is computably true.
N.Bazhenov, R.Downey, I.Kalimullin and A.Melnikov, Foundations of online structure theory, The Bulletin of Symbolic Logic25(2) (2019), 141–181. doi:10.1017/bsl.2019.20.
2.
C.Berge, Graphs and Hypergraphs, 2nd edn, North-Holland, Amsterdam, 1976.
3.
V.Brattka, G.Gherardi and A.Pauly, Weihrauch complexity in computable analysis, in: Handbook of Computability and Complexity in Analysis, V.Brattka and P.Hertling, eds, Springer, New York, 2021, In press.
4.
T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein, Introduction to Algorithms, 3rd edn, MIT Press, Massachusetts, 2009.
5.
P.C.Fishburn, Interval Orders and Interval Graphs, Wiley, New York, 1985.
6.
T.Gallai, Transitiv orientierbare Graphen, Acta Mathematica. Academiae Scientiarum Hungaricae18 (1967), 25–66, English translation in [13]. doi:10.1007/BF02020961.
7.
A.Ghouila-Houri, Caractérisation des graphes non orientés dont on peut orienter les arětes de manière à obtenir le graphe d’une relation d’ordre, Les Comptes Rendus de l’Académie des Sciences254 (1962), 1370–1371.
8.
A.Ghouila-Houri, Flots et tensions dans un graphe, Ann. Sci. École Norm. Sup. (3)81 (1964), 267–339. doi:10.24033/asens.1132.
9.
P.C.Gilmore and A.J.Hoffman, A characterization of comparability graphs and of interval graphs, Canadian Journal of Mathematics16 (1964), 539–548. doi:10.4153/CJM-1964-055-5.
10.
M.C.Golumbic, Algorithmic Graph Theory and Perfect Graphs, 2nd edn, Elsevier, 2004.
11.
E.Harzheim, Ordered Sets, Springer, New York, 2005.
12.
J.L.Hirst, Combinatorics in subsystems of second order arithmetic, PhD thesis, The Pennsylvania State University, 1987.
13.
F.Maffray and M.Preissmann, A translation of T. Gallai’s paper: “Transitiv orientierbare Graphen”, in: Perfect Graphs, J.L.Ramírez-Alfonsín and B.A.Reed, eds, Wiley, New York, 2001, pp. 25–66.
14.
S.G.Simpson, Subsystems of Second Order Arithmetic, 2nd edn, Cambridge University Press, Cambridge, 2009.
