Some New Results on Majority Coloring of Digraphs  

作　　者：Jian-sheng CAI Wei-hao XIA Gui-ying YAN 

机构地区：[1]School of Mathematics and Statistics,Weifang University,Weifang 261061,China [2]Department of Mathematics,Louisiana State University,Baton Rouge,LA 70820,USA [3]Academy of Mathematics and System Sciences,Chinese Academy of Sciences,Beijing 100190,China

出　　处：《Acta Mathematicae Applicatae Sinica》2025年第2期337-343,共7页应用数学学报(英文版)

基　　金：supported by the National Natural Science Foundation of China(No.12071351,11571258).

摘　　要：A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors.Kreutzer et al.conjectured that every digraph is majority 3-colorable.For an integer k>2,1/k-majority coloring of a directed graph is a vertex-coloring in which every vertex v has the same color as at most 1/k d^(+)(v)of its out-neighbors.Gir ao et al.proved that every digraph admits a 1/k-majority 2k-coloring.In this paper,we prove that Kreutzer’s conjecture is true for digraphs under some conditions,which improves Kreutzer’s results,also we obtained some results of 1/k-majority coloring of digraphs.Moreover,we discuss the majority 3-coloring of random digraphs with some conditions.

关 键 词：majority coloring 1/k-majority coloring DIGRAPH random digraph 

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