# Wydawnictwa / Czasopisma IMPAN / Fundamenta Mathematicae / Wszystkie zeszyty

## Fundamenta Mathematicae

Artykuły w formacie PDF dostępne są dla subskrybentów, którzy zapłacili za dostęp online, po podpisaniu licencji Licencja użytkownika instytucjonalnego. Czasopisma do 2009 są ogólnodostępne (bezpłatnie).

## On generalized shift graphs

### Tom 226 / 2014

Fundamenta Mathematicae 226 (2014), 173-199 MSC: Primary 05C15; Secondary 05C63. DOI: 10.4064/fm226-2-6

#### Streszczenie

In 1968 Erd{ő}s and Hajnal introduced shift graphs as graphs whose vertices are the $k$-element subsets of $[n]=\{1,\dots ,n\}$ (or of an infinite cardinal $\kappa$) and with two $k$-sets $A=\{a_1,\dots ,a_{k}\}$ and $B=\{b_1,\dots ,b_{k}\}$ joined if $a_1< a_2=b_1< a_3=b_2< \cdots < 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 $\kappa$ and integer $l$, there exists a graph $G$ with $|V(G)|=\chi (G)=\kappa$ but such that, for any finite subgraph $F\subset G$, $\chi (F)\leq \log_{(l)}|V(F|$, where $\log_{(l)}$ is the $l$-iterated logarithm. This answers a question raised by Erdős, Hajnal and Shelah.

#### Autorzy

• Christian AvartDepartment of Mathematics and Statistics
Georgia State University
Atlanta, GA 30303, U.S.A.
e-mail
• Tomasz ŁuczakFaculty of Mathematics and CS
61-614 Poznań, Poland
e-mail
• Vojtěch RödlDepartment of Mathematics and CS
Emory University
Atlanta, GA 30322, U.S.A.
e-mail

## Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

## Przepisz kod z obrazka Odśwież obrazek