报告题目：Hardness and Approximation for Coloring Digraphs

报告人：唐朝亮 复旦大学

报告时间：5月26日 2:00

报告地点：五教5305

摘要：We study the dichromatic number and acyclic number of digraphs from an approximation perspective. First, we show that even for tournaments, approximating these parameters is as hard as for undirected graphs: for any \(\epsilon > 0\), neither \(\alphav\) nor \(\chiv\) can be approximated within a factor of \(n^{1-\epsilon}\) in tournaments, unless \(\textsf{P} = \textsf{NP}\). Next, we consider approximate coloring in special cases. We prove that any \(\ell\)-dicolorable digraph can be colored with at most \(\ell \cdot n^{1-1/\ell}\) colors in \(O(n^{2\ell})\) time; in particular, \(2\)-dicolorable digraphs can be colored with \(2\sqrt{n}\) colors in polynomial time. Finally, we bound the dichromatic number of dense digraphs in terms of the independence number \(\alpha\) of the underlying undirected graph. We focus on two cases: digraphs with \(\chiv(D) \leq 2\) and digraphs with no directed triangle. For these, we give algorithms that generalize and improve existing tools and results.

简介：唐朝亮，复旦大学上海数学中心博士研究生，研究方向为结构与极值图论，导师吴河辉教授。研究方向涉及线性图兰数、有序图区间子式、有向图染色等，相关论文已在ICALP、APPROX等会议以及EJC等期刊接收或发表，并多次在国内外学术会议中作报告。