학과 세미나 및 콜로퀴엄
2024-09 | ||||||
---|---|---|---|---|---|---|
Sun | Mon | Tue | Wed | Thu | Fri | Sat |
1 | 2 | 3 1 | 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 |
Room B332, IBS (기초과학연구원)
이산수학
Amadeus Reinald (LIRMM, Université de Montpellier, CNRS)
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$.