Seminar

# On the chromatic number of generalized shift graphs

#### Tomasz Luczak - Adam Mickiewicz University

For natural numbers $k$ and $n$, by $G(n,\delta_k)$ we denote the graph whose vertex set consists of all $k$-element subsets of ${1,2,\dots,n}$, and two subsets $A={a_1,a_2\,dots,a_k}$ and $B={b_1,b_2,\dots, b_k}$ are adjacent if $a_1<{a_2}<{b_1}<{a_3}<{b_2}<{a_4}<{b_3}<{\cdots}<{a_k}<{b_{k-1}}<{b_k}$ In the talk we try to estimate the chromatic number of $G(n,\delta_k)$. This is a joint work with Christian Avart and Vojta Rodl.
Organizers
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski