Partitions and orientations of the Rado graph

4 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We classify the countably infinite oriented graphs which, for every partition of their vertex set into two parts, induce an isomorphic copy of themselves on at least one of the parts. These graphs are the edgeless graph, the random tournament, the transitive tournaments of order type~$\omega^\alpha$, and two orientations of the Rado graph: the random oriented graph, and a newly found random acyclic oriented graph.
Document type :
Journal articles

Cited literature [11 references]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00153515
Contributor : Stephan Thomasse <>
Submitted on : Friday, December 14, 2007 - 1:42:45 PM
Last modification on : Friday, September 18, 2020 - 6:06:02 PM
Long-term archiving on: : Thursday, April 8, 2010 - 5:23:12 PM

Citation

Reinhard Diestel, Imre Leader, Alex Scott, Stéphan Thomassé. Partitions and orientations of the Rado graph. Transactions of the American Mathematical Society, American Mathematical Society, 2007, 359, pp.2395-2405. ⟨10.1090/S0002-9947-06-04086-4⟩. ⟨lirmm-00153515⟩

Record views