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-maj...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.展开更多
基金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.
