Loading Events

« All Events

  • This event has passed.
:

James Davies, Separating polynomial $\chi$-boundedness from $\chi$-boundedness

Thursday, February 10, 2022 @ 4:30 PM - 5:30 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)

We prove that there is a function $f : \mathbb{N} \to \mathbb{N}$ such that for every function $g : \mathbb{N} \to \mathbb{N} \cup \{\infty\}$ with $g(1)=1$ and $g \ge f$, there is a hereditary class of graphs $\mathcal{G}$ such that for each $\omega \in \mathbb{N}$, the maximum chromatic number of a graph in $\mathcal{G}$ with clique number $\omega$ is equal to $g(\omega)$. This extends a recent breakthrough of Carbonero, Hompe, Moore, and Spirk. In particular, this proves that there are hereditary classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded.

Joint work with Marcin Briański and Bartosz Walczak.

Details

Date:
Thursday, February 10, 2022
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.