The Library
Isometric copies of directed trees in orientations of graphs
Tools
Banakh, Taras, Idzik, Adam, Pikhurko, Oleg, Protasov, Igor and Pszczola, Krzysztof (2020) Isometric copies of directed trees in orientations of graphs. Journal of Graph Theory, 94 (2). pp. 175-191. doi:10.1002/jgt.22513 ISSN 0364-9024.
|
PDF
WRAP-isometric-copies-trees-orientations-graphs-Pikhurko-2019.pdf - Accepted Version - Requires a PDF viewer. Download (774Kb) | Preview |
Official URL: https://doi.org/10.1002/jgt.22513
Abstract
The isometric Ramsey number IR( ~ H) of a family ~ H of digraphs is the smallest number of vertices in a graph G such that any orientation of the edges of G contains every member of ~ H in the distance-preserving way. We observe that for any finite family ~ H of finite acyclic graphs the isometric Ramsey number IR( ~ H) is finite, and present upper bounds for IR( ~ H) in some special cases. For example, we show that the isometric Ramsey number of the family of all oriented trees with n vertices is at most n2n+o(n).
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||
Library of Congress Subject Headings (LCSH): | Directed graphs, Trees (Graph theory), Graph coloring, Isometrics (Mathematics) , Graph theory | |||||||||
Journal or Publication Title: | Journal of Graph Theory | |||||||||
Publisher: | John Wiley & Sons Ltd. | |||||||||
ISSN: | 0364-9024 | |||||||||
Official Date: | June 2020 | |||||||||
Dates: |
|
|||||||||
Volume: | 94 | |||||||||
Number: | 2 | |||||||||
Page Range: | pp. 175-191 | |||||||||
DOI: | 10.1002/jgt.22513 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Reuse Statement (publisher, data, author rights): | "This is the peer reviewed version of the following article: Banakh, T, Idzik, A, Pikhurko, O, Protasov, I, Pszczoła, K. Isometric copies of directed trees in orientations of graphs. J Graph Theory. 2019; 1– 17, which has been published in final form at https://doi.org/10.1002/jgt.22513. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions." | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 17 October 2019 | |||||||||
Date of first compliant Open Access: | 8 November 2020 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year