BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20240903T163000
DTEND;TZID=Asia/Seoul:20240903T173000
DTSTAMP:20260415T201649
CREATED:20240319T124710Z
LAST-MODIFIED:20240707T023848Z
UID:8360-1725381000-1725384600@dimag.ibs.re.kr
SUMMARY:Amadeus Reinald\, Oriented trees in $O(k \sqrt{k})$-chromatic digraphs\, a subquadratic bound for Burr's conjecture
DESCRIPTION: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. \nIn 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$.
URL:https://dimag.ibs.re.kr/event/2024-09-03/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR