Research On Some Out-degree Conditions Coloring Of Digraphs

Graph coloring theory is an important branch of graph theory,which plays an important role in neural network problems,programming problems,optimization problems and communication engineering,etc.In the hundreds of years of research and development of graph theory,it has produced many different branches,such as coloring theory,factor theory,etc.,where coloring theory includes that vertex coloring problem,edge coloring problem,total coloring problem and acyclic coloring problem,etc.The graph coloring theory is one of the most important branches in graph theory.Actually,the vertex coloring problem of graph is one of the most active areas of graph theory research.However,the coloring problem of digraph is a problem proposed in recent decades,which is closely related to computer science and complex networks,etc.And coloring of digraph is the foundation of the development of computer science.In 2016,Kreutzer et al.proposed the majority coloring of digraphs.After research,they proved that any digraphis majority 4-colorable,and conjectured that any digraphis majority 3-coloring.Meanwhile,Kreutzer et al.generalized majority coloring,gave the definition of1/k-majority coloring,and conjectured that any digraphis1/k-majority (2k-1)-coloring.In the same year,Anholcer et al.proposed the concept of majority list coloring and conducted a series of research work.This paper mainly studies the coloring problems of majority coloring,1/k-majority coloring and majority list coloring for digraphs under the degree condition,and the constraints of majority coloring conjecture and1/k-majority coloring conjecture have been improved.The main body of this paper consists of following five chapters:In the first chapter,we mainly introduced some basic concepts and related research background and research significance of the vertex coloring problem of digraphs.In the second chapter,the probabilistic method is mainly used to study the majority coloring of digraphs under degree conditions,and we also studied tournaments,-regular digraphs and random digraphs,and we improved the results of majority coloring of tournaments,-regular digraphs and random digraphs.In the third chapter,the probabilistic method is mainly used to study the1/k-majority coloring of digraphs under out-degree conditions,and we also studied tournaments and random digraphs,and we improved the results of1/k-majority coloring of tournaments and random digraphs.In the fourth chapter,we mainly using discharge techniques,it is proved that 1-planar digraphs without 4-cycle and NIC-planar digraphs are majority 3-list coloring.In the fifth chapter,we summarized the paper and briefly introduces the unsolved problems and the research problems that can be carried out in the future.