Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated

Claims

../

1978_11_01_nesetril_rodl: Corollary 3 of Nešetřil and Rödl (Proc. Amer. Math. Soc. 1978) gives, for every s, a graph of girth s in which every vertex ordering has a monotone s-path closed into an s-cycle by the edge joining its ends; accepted.

1987_01_01_pretzel: Pretzel constructs a graph of girth 6 that cannot be oriented as the diagram of an ordered set, so it has no acyclic orientation that stays acyclic after any one edge is reversed.