Conflict-free Connection Number Of Graphs With Degree Conditions

Graph theory is a new branch of mathematics,which is widely used in many fields,such as physics,chemistry,operations research,computer science,information theory,cybernetics,network theory,social science and economic management.In this thesis,we focus on graph coloring.Many practical problems are closely related to graph coloring theory,such as communication networks,transportation,exam scheduling,chemical and biological information computing,etc.We introduce the basic knowledge of graphs and some conclusions related to the research of graph coloring,and then analyze some conflict-free connection numbers of minimum degree δ(G)and maximum degree Δ(G).The main contents are as follows:In the first chapter,we introduce some basic concepts and related notations in graph theory and basic results on the theory of graph conflict-free coloring.In the second chapter,we studied the problem of the conflict-free connection number of the minimum degree of graph,obtain the upper bound of the noncontradictory connected number by using the structural characteristics of the graph,and describe the minimum degree conditions of several kinds of graphs with conflict-free connection number of 2 and 3.In the third chapter,we discussed the conflict-free connection number of trees with maximum degree 3 and conflict-free connection number at most 4,and finally we studied some graph classes with conflict-free connection number at most 4.In the fourth chapter,we studied the conflict-free connection numbers of special graphs such as spider graphs and caterpillar graphs.In the fifth chapter,according to the conclusion of conflict-free coloring,the upper bound of the conflict-free connection number of trees is characterized by the matching number of graphs.In the sixth chapter,we summarized the content of this thesis and prospected the potential problems.In short,this thesis mainly studies the conflict-free connection number of graphs with minimum degree and maximum degree.The research results provide theoretical support for the promotion and application of conflict-frees coloring,and also have important reference significance for coloring theory.