On generalized shift graphs

• Autorzy: Christian Avart , Tomasz Łuczak , Vojtěch Rödl
• Języki publikacji: EN

Abstrakty

EN

In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = {1,...,n} (or of an infinite cardinal κ ) and with two k-sets $A = {a₁,...,a_{k}}$ and $B = {b₁,...,b_{k}}$ joined if $a₁ < a₂ = b₁ < a₃ = b₂ < ⋯ < a_k = b_{k-1} < b_k$. They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with interesting disparity of chromatic behavior of finite and infinite subgraphs. For any cardinal κ and integer l, there exists a graph G with |V(G)| = χ(G) = κ but such that, for any finite subgraph F ⊂ G, $χ(F)≤ log_{(l)}|V(F|$, where $log_{(l)}$ is the l-iterated logarithm. This answers a question raised by Erdős, Hajnal and Shelah.

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C63: Infinite graphs

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 2014
• Tom: 226
• Numer: 2
• Strony: 173-199

Daty

wydano

2014

Twórcy

autor

Christian Avart

• Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, U.S.A.

autor

Tomasz Łuczak

• Faculty of Mathematics and CS, Adam Mickiewicz University, 61-614 Poznań, Poland

autor

Vojtěch Rödl

• Department of Mathematics and CS, Emory University, Atlanta, GA 30322, U.S.A.

Identyfikatory

DOI

10.4064/fm226-2-6