Majority Coloring of r-Regular Digraph

XIA Wei-hao, SHI Mei, XIAO Ming-yue, CAI Jian-sheng, WANG Ji-hui

doi:10.13371/j.cnki.chin.q.j.m.2022.02.004

Chinese Quarterly Journal of Mathematics >

2022 , Vol. 37 >Issue 2: 142 - 146

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2022.02.004

Majority Coloring of r-Regular Digraph

Expand

1. School of Mathematical Sciences, University of Jinan, Jinan 250022, China; 2. School of Mathematics and Information Sciences, Weifang University, Weifang 261061, China

XIA Wei-hao (1998-), male, native of Kunming, Yunnan, postgraduate of University of Jinan, engages in graph theory research; SHI Mei (1997-), female, native of Taian, Shandong, postgraduate of University of Jinan, engages in graph theory research; XIAO Ming-yue (1998-), female, native of Jinan, Shandong, postgraduate of University of Jinan, engages in graph theory research; CAI Jian-sheng (1966-), male, native of Weifang, Shandong, professor of Weifang University, engages in graph theory research; WANG Ji-hui (1972-), male, native of Jinan, Shandong, professor of University of Jinan, engages in graph theory research.

Received date: 2021-11-29

Online published: 2022-06-30

Supported by

Supported by the National Natural Science Foundation of China (Grant No. 12071351) and
the Natural Science Foundation of Shandong Provence (Grant No. ZR2020MA043).

Fold

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

Cite this article

XIA Wei-hao, SHI Mei, XIAO Ming-yue, CAI Jian-sheng, WANG Ji-hui . Majority Coloring of r-Regular Digraph[J]. Chinese Quarterly Journal of Mathematics, 2022 , 37(2) : 142 -146 . DOI: 10.13371/j.cnki.chin.q.j.m.2022.02.004

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article