Strong Erd\H{o}s-Hajnal properties in chordal graphs

Thời gian: 09:00 đến 11:30 Ngày 21/04/2023

Địa điểm: Gwangju Institute of Science and Technology, Korea

Dear all:
It is my pleasure to invite you to the following talk of the Korea-Taiwan-Vietnam Joint Seminar in Combinatorics and Analysis.

Friday, April 21 at 09:00 am Hanoi time
Speaker: Minki Kim (Gwangju Institute of Science and Technology, Korea)

Title: Strong Erd\H{o}s-Hajnal properties in chordal graphs

Abstract: A graph class is said to have the strong Erd\H{o}s-Hajnal property (SEH property) if, for every graph in the class, the graph itself or its complement contains a balanced complete bipartite graph of linear size. Recently, we obtain a quantitatively tight result on the SEH property of chordal graphs. In addition, we discuss a colored version of this property for chordal graphs with bounded leafage. In particular, we show that for every pair $F_1, F_2$ of subtree families in a tree with $k$ leaves, there exist subfamilies $F_1' \subset F_1$ and $F_2' \subset F_2$ with $|F_i'| = \Theta\left(\frac{\log{k}}{k}|F_i| \right)$ such that either every colorful pair is intersecting or there is no intersecting colorful pair. This is joint work with Minho Cho, Andreas Holmsen, and Jinha Kim.

ZOOM link: https://us02web.zoom.us/j/87167950828?pwd=UFpHTkcwaDZWTndsRGloRE5yN2tIdz09
Zoom Meeting ID: 871 6795 0828
Passcode: 352266