Loading Events

« All Events

  • This event has passed.

Linda Cook, Orientations of $P_4$ bind the dichromatic number

Tuesday, August 22, 2023 @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)


Linda Cook
IBS Discrete Mathematics Group

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.

The 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))$.

Aboulker, 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$.

In 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.


Tuesday, August 22, 2023
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원) + Google Map


Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.