| Title | : | Variants of the Gyarfas-Sumner Conjecture |
| Speaker | : | Mathew Francis (Associate Professor, ISI Chennai) |
| Details | : | Tue, 14 Nov, 2023 11:00 AM @ SSB 334 |
| Abstract: | : | Given graphs G and H, we say that G is H-free if G does not contain any subgraph isomorphic to H. The Gyarfas-Sumner conjecture states that for every pair of integers s,t, there exists an integer f(s,t) such that every Kt-free graph having chromatic number at least f(s,t) contains every tree on s vertices as an induced subgraph. A vertex-colored graph H is called "rainbow" if no two vertices of H have the same color. A stronger "rainbow" variant of the conjecture could be as follows: Is it true that in every properly coloured Kt-free graph of sufficiently high chromatic number, there exists every tree on s vertices as an induced rainbow subgraph? Kierstead and Trotter showed that this is not true by showing the existence of properly coloured triangle-free graphs of arbitrarily high chromatic number that do not contain even a rainbow claw as a subgraph. However, if we restrict the trees that we seek to just paths, then the answer is positive: Scott and Seymour showed that every properly coloured Kt-free graph containing no path on s vertices as an induced rainbow subgraph has bounded chromatic number. Bounds on the chromatic number better than the ones given by Scott and Seymour exist for graphs of girth at least 5: it follows from the work of Gyarfas and Sarkozy that every properly coloured graph of girth at least 5 and containing a no induced rainbow path on s vertices has chromatic number O((2s)2s). We improve this bound by showing that every properly coloured C4-free graph containing no induced rainbow path on s vertices has chromatic number at most (s2+s)/2. We then show that better upper bounds on the chromatic number can be obtained for graphs of larger girth: we show that every properly coloured graph having girth g and containing no induced rainbow path on s vertices has chromatic number at most s1+4/(g-4) . Along the way, we obtain some new results regarding an "oriented" variant of the Gyarfas-Sumner conjecture, discovering some classes of oriented graphs for which the absence of any particular oriented tree as an induced subgraph implies a bounded chromatic number. |
