Loading Events

« All Events

  • This event has passed.

Paul Seymour, Polynomial bounds for chromatic number

Friday, October 8, 2021 @ 10:00 AM - 11:00 AM KST

Zoom ID: 869 4632 6610 (ibsdimag)


Paul Seymour
Department of Mathematics, Princeton University

The Gyárfás-Sumner conjecture says that for every forest $H$, there is a function $f$ such that the chromatic number $\chi(G)$ is at most $f(\omega(G))$ for every $H$-free graph $G$ (“$H$-free” means with no induced subgraph isomorphic to $H$, and $\omega(G)$ is the size of the largest clique of $G$). This well-known conjecture has been proved only for a few types of forest.

Nevertheless, there is a much stronger conjecture, due to Esperet: that for every forest $H$, there is a polynomial function $f$ as above. As one might expect, this has been proved for even fewer types of forest; and the smallest tree $H$ for which Esperet’s conjecture is not known is the five-vertex path $P_5$.

A third notorious conjecture is the Erdős-Hajnal conjecture, that for every graph $H$, there exists $c>0$ such that $\alpha(G)\omega(G)\ge |G|^c$ for every $H$-free graph $G$ (where $\alpha(G)$ is the size of the largest stable set of $G$). The smallest graph $H$ for which this is not known is also $P_5$, which, conveniently, is a forest; and every forest that satisfies Esperet’s conjecture also satisfies the Erdős-Hajnal conjecture. So there is substantial interest in the chromatic numbers of $P_5$-free graphs. The best upper bound that was previously known, due to Esperet, Lemoine, Maffray, and Morel, was that $\chi(G)\le (5/27)3^\omega(G)$ for every $P_5$-free graph $G$ with $\omega(G) > 2$. In recent work with Alex Scott and Sophie Spirkl, we have proved several results related to Esperet’s conjecture, including proofs of its truth for some new types of forest $H$, and a “near-polynomial” bound when $H = P_5$, that $\chi(G) \le \omega(G)^{\log_2(\omega(G))}$ for every $P_5$-free graph $G$ with $\omega(G) > 2$. We survey these results and give a proof of the new bound for $P_5$.


Friday, October 8, 2021
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:


Zoom ID: 869 4632 6610 (ibsdimag)


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.