Majority Coloring of r-Regular Digraph  

r-正则有向图的多数染色

作　　者：XIA Wei-hao SHI Mei XIAO Ming-yue CAI Jian-sheng WANG Ji-hui 夏伟皓;石美;肖明月;蔡建生;王纪辉(School of Mathematical Sciences,University of Jinan,Jinan 250022,China;School of Mathematics and Information Sciences,Weifang University,Weifang 261061,China)

机构地区：[1]School of Mathematical Sciences,University of Jinan,Jinan 250022,China [2]School of Mathematics and Information Sciences,Weifang University,Weifang 261061,China

出　　处：《Chinese Quarterly Journal of Mathematics》2022年第2期142-146,共5页数学季刊（英文版）

基　　金：Supported by the National Natural Science Foundation of China(Grant No.12071351);the Natural Science Foundation of Shandong Provence(Grant No.ZR2020MA043).

摘　　要：A majority k-coloring of a digraph D with k colors is an assignment c:V(D)→{1,2,…,k},such that for every v∈V(D),we have c(w)=c(v)for at most half of all out-neighbors w∈N^(+)(v).For a natural number k≥2,a 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 1/k proportion of its out-neighbours.Kreutzer,Oum,Seymour,van der Zypen and Wood proved that every digraph has a majority 4-coloring and conjectured that every digraph admits a majority 3-coloring.Gireao,Kittipassorn and Popielarz proved that every digraph has a 1/k-majority 2k-coloring and conjectured that every digraph admits a 1/k majority(2k-1)-coloring.We showed that every r-regular digraph D with r>36ln(2n)has a majority 3-coloring and proved that every digraph D with minimum outdegreeδ+>2k2(2k-1)/(k-1)^(2)ln2(n)[(2k-1)n]has a 1/k-majority(2k-1)-coloring.We showed that every r-regular digraph D with r>36ln(2n)has a majority 3-coloring and proved that every digraph D with minimum outdegreeδ+>,2k^(2)(2k-1)^(2)/(k-1)^(2)ln[(2k-1)n]has a 1/k-majority(2k-1)-coloring.And we also proved that every r-regular digraph D with r>3k^(2)(2k-1)/(k-1)^2ln(2n)has a 1/k-majority(2k-1)-coloring.

关 键 词：Majority coloring Regular digraph 1/k-Majority coloring 

分 类 号：O157.5[理学—数学]