MATEC Web of Conferences (Jan 2022)

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

  • Shi Mei,
  • Xia Weihao,
  • Xiao Mingyue,
  • Wang Jihui

DOI
https://doi.org/10.1051/matecconf/202235502004
Journal volume & issue
Vol. 355
p. 02004

Abstract

Read online

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.