On ordered graphs and graph orderings
type: Item
instance of: scholarly article
title: On ordered graphs and graph orderings
zbMATH Open document ID: 0802.05055
DOI: 10.1016/0166-218X(94)90100-7
author: J. Nešetřil
published in: Discrete Applied Mathematics
publication date: 1994-07-31T00:00:00Z
review text: The main result of this paper is: For every oriented graph \(\vec G\) with in-degree for every vertex at least 2 there is no graph \(H\) such that every strong orientation \(\vec H\) of \(H\) contains a copy of \(\vec G\). This disproves a conjecture of \textit{M. Cochand} and \textit{P. Duchet} [Algorithms Comb. 8, 39-46 (1989; Zbl 0698.05055)]. The author also discusses the relationship of the above result and similar results with Ramsey theory.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 612436
zbMATH Keywords: ordered graphs
zbMATH Keywords: graph orderings
zbMATH Keywords: oriented graph
zbMATH Keywords: strong orientation
zbMATH Keywords: Ramsey theory
reviewed by: Jack E. Graver
MaRDI profile type: Publication
cites work: Q3475303
cites work: Q4056030
cites work: Q4088855
cites work: Q4088856
cites work: On a Probabilistic Graph-Theoretical Method
cites work: Q3872505
cites work: A Ramsey-Type Theorem for Orderings of a Graph
cites work: Q4103570
full work available at URL: 0166-218x(94)90100-7
OpenAlex ID: W2169976885
description: scientific article; zbMATH DE number 612436