关键词: Majority coloring, Regular digraph,  1/k-Majority coloring

Abstract:  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. Gir$\widetilde{a}$o, 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
$\delta^+>\frac{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>\frac{3k^2(2k-1)}{(k-1)^2} \ln(2n)$ has a 1/k-majority (2k−1)-coloring.

Key words: Majority coloring, Regular digraph,  1/k-Majority coloring