报告题目：Majority coloring of digraphs

报告人：蔡建生

报告时间：2022年11月12日上午9：30-10：30

报告地点：腾讯会议742 746 851

报告摘要：A majority $k$-coloring of a digraph $D$ with $k$ colors is an assignment $c:V(D) \rightarrow \{1,2,\cdots ,k\}$, such that for every $v\in V(D)$, we have $c(w)=c(v)$ for at most half of all out-neighbors $w\in N^+(v)$. Kreutzer et al. conjectured that every digraph admits a majority 3-coloring. For a natural number $k\geq 2$, a $\frac{1}{k}$-majority coloring of a digraph is a coloring of the vertices such that each vertex receives the same color as at most a $\frac{1}{k}$ proportion of its out-neighbours. Gir$\widetilde{a}$o et al. conjectured that every digraph admits a $\frac{1}{k}$-majority $(2k-1)$-coloring. In this paper, we prove that Kreutzer's conjecture is true for digraphs under some conditions, which improves Kreutzer's results. Moreover, we discuss the majority 3-coloring of random digraph with some conditions.

个人简介：蔡建生，潍坊学院数学与信息科学学院教授，理学博士，中国工业与应用数学学会图论组合及其应用专业委员会常务委员、信息与通讯领域的数学专业委员会委员、山东数学会高等数学专业委员会常务理事。常年从事图论及其应用的研究，发表相关学术论文50余篇，出版学术专著1部，2016年以来主持国家自然科学基金面上项目2项，参与多项，主持山东省自然科学基金面上项目2项。

蔡建生教授目前的研究兴趣主要在于图染色理论和概率方法，主持的研究成果一次获得山东省自然科学奖、两次获山东省高等学校优秀科研成果奖。