학과 세미나 및 콜로퀴엄
2024-08 | ||||||
---|---|---|---|---|---|---|
Sun | Mon | Tue | Wed | Thu | Fri | Sat |
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Room B332, IBS (기초과학연구원)
이산수학
Amadeus Reinald (Université de Montpellier)
Oriented trees in O(k sqrt k)-chromatic digraphs, a subquadratic bound for Burr’s conjecture
Room B332, IBS (기초과학연구원)
이산수학
In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which was improved in 2013 to $\frac{k^2}{2} - \frac{k}{2} + 1$ by Addario-Berry et al.
In this talk, we give the first subquadratic bound for Burr's conjecture, by showing that every directed graph with chromatic number $8\sqrt{\frac{2}{15}} k \sqrt{k} + O(k)$ contains any oriented tree of order $k$. Moreover, we provide improved bounds of $\sqrt{\frac{4}{3}} k \sqrt{k}+O(k)$ for arborescences, and $(b-1)(k-3)+3$ for paths on $b$ blocks, with $b\ge 2$.