| As an important branch of combinatorial mathematics,graph theory is widely used in management science,computer science and technology,communication engineering and other fields.In the research process of graph theory,it has produced many different branches,such as graph coloring theory,random graph theory,extreme value graph theory,etc.The coloring problem of graphs is an important research direction in graph theory,and the vertex coloring problem of graphs is one of the most active areas of graph theory research.The majority coloring of digraphs is a new problem raised in recent years,which is closed related to complex networks,blockchain design technology,bioinformatics and other fields,and has important theoretical value and application background.With the deepening of research,the theorem that every digraph is majority 4-colorable has been proved,and it is conjectured that three colors are sufficient.Scholars have successively verified and improved this conjecture,and studied the relationship between the majority coloring of digraphs and several other vertex coloring.This paper mainly studies the majority coloring problem of the join graph of some special digraphs and several kinds of product graphs,and verify the above conjecture.The main body of this paper consists of four parts:The first part mainly introduces some basic concepts and related research background and research significance of the vertex coloring problem of digraphs.The second part mainly studies the majority coloring of the join graphs of some special digraph,and studies this problem according to the structural characteristics of the join graphs.The third part mainly studies the majority coloring of several types of product graphs of some special digraphs,which are mainly divided into: directed product graphs,Cartesian product graphs,strong product graphs and lexicographic product graphs.According to the unique structure of each class of product graphs and the relationships that exist between them,the majority coloring problem of these graphs is studied.The fourth part summarizes the paper and briefly introduces the unsolved problems and the research problems that can be carried out in the future. |
