Authors: Di Prisco, Carlos
Todorčević, Stevo 
Title: Shift graphs on precompact families of finite sets of natural numbers
Journal: Discrete Mathematics
Volume: 312
Issue: 19
First page: 2915
Last page: 2926
Issue Date: 6-Oct-2012
Rank: M22
ISSN: 0012-365X
DOI: 10.1016/j.disc.2012.05.010
We study graphs defined on families of finite sets of natural numbers and their chromatic properties. Of particular interest are graphs for which the edge relation is given by the shift. We show that when considering shift graphs with infinite chromatic number, one can center attention on graphs defined on precompact thin families. We define a quasi-order relation on the collection of uniform families defined in terms of homomorphisms between their corresponding shift graphs, and show that there are descending ω1-sequences. Specker graphs are also considered and their relation with shift graphs is established. We characterize the family of Specker graphs which contain a homomorphic image of a shift graph.
Keywords: Shift graphs
Publisher: Elsevier
Project: CNRS-FONACIT, Grant PI2009000240
NSERC, Grant 455916

Show full item record


checked on May 20, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.