The majority coloring of the join and Cartesian product of some digraph

Abstract

A majority coloring of a digraph is a vertex coloring such that for every vertex, the number of vertices with the same color in the out-neighborhood does not exceed half of its out-degree. Kreutzer, Oum, Seymour and van der Zyper proved that every digraph is majority 4-colorable and conjecture that every digraph has a majority 3-coloring. This paper mainly studies the majority coloring of the joint and Cartesian product of some special digraphs and proved the conjecture is true for the join graph and the Cartesian product. According to the influence of the number of vertices in digraph, we prove the majority coloring of the joint and Cartesian product of some digraph.