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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230822T163000
DTEND;TZID=Asia/Seoul:20230822T173000
DTSTAMP:20260419T022150
CREATED:20230425T022914Z
LAST-MODIFIED:20240707T073336Z
UID:7057-1692721800-1692725400@dimag.ibs.re.kr
SUMMARY:Linda Cook\, Orientations of $P_4$ bind the dichromatic number
DESCRIPTION:An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. \nThe Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs\, which states that for any forest $F$\, there is some function $f$ such that every $F$-free graph $G$ with clique number $\omega(G)$ has chromatic number at most $f(\omega(G))$. \nAboulker\, Charbit\, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph $D$ is the minimum number of colors required to color the vertex set of $D$ so that no directed cycle in $D$ is monochromatic. Aboulker\, Charbit\, and Naserasr’s $\overrightarrow{\chi}$-boundedness conjecture states that for every oriented forest $F$\, there is some function $f$ such that every $F$-free oriented graph $D$ has dichromatic number at most $f(\omega(D))$\, where $\omega(D)$ is the size of a maximum clique in the graph underlying $D$. \nIn this talk\, we perform the first step towards proving Aboulker\, Charbit\, and Naserasr’s $\overrightarrow{\chi}$-boundedness conjecture by showing that it holds when $F$ is any orientation of a path on four vertices.
URL:https://dimag.ibs.re.kr/event/2023-08-22/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR