Seminar

On the chromatic number of generalized shift graphs

Graphs, Hypergraphs, and Computing

18 February 14:00 - 15:00

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
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU

Program
Contact

Klas Markström

klas.markstrom@math.umu.se

Other
information

For practical matters at the Institute, send an e-mail to secretary@mittag-leffler.se