Title: Oriented and Colorful Variants of Gyárfás–Sumner Conjecture
Speaker: Sunil Chandran (IISc CSA)
Date: 11 December 2019
Time: 3 pm
Venue: LH-1, Mathematics Department
The Gyárfás–Sumner conjecture states the following: Let $a,b$ be
positive integers. Then there exists a function $f$, such that if
$G$ is a graph of clique number at most $a$ and chromatic number at
least $f(a,b)$, then $G$ contains all trees on at most $b$ vertices
as induced subgraphs. This conjecture is still open, though for
several special cases it is known to be true. We study the oriented
version of this conjecture: Does there exist a function $g$, such
that if the chromatic number of an oriented graph $G$ (satisfying
certain properties) is at least $g(s)$ then $G$ contains all
oriented trees on at most $s$ vertices as its induced subgraphs. In
general this statement is not true, not even for triangle free graphs.
Therefore, we consider the next natural special class – namely the
4-cycle free graphs – and prove the above statement for that class.
We show that $g(s) \leq 4s^2$ in this case.
We also consider the rainbow (colorful) variant of this conjecture.
As a special case of our theorem, we significantly improve an earlier
result of Gyárfás and Sarkozy regarding the existence of induced
rainbow paths in $C_4$ free graphs of high chromatic number. I will
also discuss the recent results of Seymour, Scott (and Chudnovsky)
on this topic.