Groupe

GT

Seminars are given every Friday from 2:00 to 3:00 (usually in room 178, but not for the time being). You are welcome 10 minutes earlier for (temporarily virtual) tea, coffee and cake.

In order to receive the announcements, just send an email to sympa@diff.u-bordeaux.fr with subject "subscribe labri.go-gt Cookie Monster", where Cookie is your first name and Monster your last name.

See the agenda of the seminars: webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.html https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.html; to add it to yours webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.ics https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics , or flash the following QRCode:

Next talks:

The talks are now also available online : https://webconf.u-bordeaux.fr/b/mar-ef4-zed.

Vendredi 21 janvier 14h - Marek Sokołowski
Graphs of bounded twin-width are quasi-polynomially chi-bounded
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
We prove that for every $t \in \N$ there is a constant $c_t$ such that every graph with twin-width at most $t$ and clique number $\omega$ has chromatic number bounded by $2^{c_t \log^{O(t)} \omega}$. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially $\chi$-bounded. This provides a partial resolution of a conjecture of Bonnet et al. [SODA 2021] that they are polynomially $\chi$-bounded.

This is a joint work with Michal Pilipczuk.

Jobs

Group

GT Graphs and Optimization

History

 Previous Years

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki