报告题目 (Title)：有向图的Majority染色数的界刻画（New bounds on Majority coloring of digraphs )
报告人 (Speaker)：蔡建生 教授（潍坊学院）
报告时间 (Time)：2023年04月13日(周四) 10:00-11:00
报告地点 (Place)：校本部F309
邀请人(Inviter)：袁西英
主办部门：理学院数学系
报告摘要：Title Abstract: 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.
