Algebra & Combinatorics Seminar

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.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 05 Dec 2019