Dynamic Coloring Of Some Graph Classes

Graph theory originated from the Konigsberg Seven Bridges problem,which is an important branch of mathematics.As one of the three major mathematical problems in modern world,the Four-Color Conjecture promoted the development of graph theory,especially the coloring theory of graphs,plane graph theory,and algebra.The development of branches such as topology has played an important role in promoting.The coloring theory of graphs is a branch of graph theory,which not only enriches the content of graph theory,but also effectively solves the planning and scheduling problems in reality.Later,the coloring theory of graphs is derived many directions,for example,acyclic coloring,uniform coloring,restricted coloring,distance coloring,total coloring,etc.In 2001,Lai and Montgomery first proposed the concept of dynamic coloring and proved the bound of 2-dynamic coloring connected with G.Subsequently.The results of the research of dynamic coloring emerge in endlessly.This article focuses on the research of dynamic coloring.The graphs studied in this article are all undirected and finite non-empty graphs.G=(V,E)represents a graph,where V=V(G)and E=E(G)are used to represent the graph respectively G vertex set and edge set.We use ?(G),?(G)to denote the maximum degree and minimum degree of the graph G respectively.Let two integers r,k?1,[k]=?1,2,3,…,k}.If c:V(G)?[k],the graph G satisfies two conditions.First,on any v1v2? E(G),then c(v1)?(v2).Second,for any v ? V(G),then|c(NG(v))|? min{d(v),r?.Then,we call the c is the r-dynamic coloring of graph.Subsequently,the researchers focused on Cn graphs,bipartite graphs,claw-free graphs,Pn-free and other general graph classes for further discussion.In 2017,Bowler considered any positive integers of n? 2,and came up with ?2(G)=2n.In 2015,Jahanbekam et al.proved that the result of 3-dynamic 2-grids are ?_r(G_m,n)?5.In 2018,Song et al.found that when r?8,the result of the floor plan G are ?_r(G)?2r+16.In 2019,Zhang and Li proved that when G is 1-planar,chr(G)?11.In 2020,Zhu and Bu obtained the general result of the dynamic chromatic number of the list of sparse graphs.We start from the existing research results and derive some new results.This paper studies the dynamic coloring of graphs are 2-grids,3-grids,n-grids,and 1-planar graphs.The chapter 1 focuses on the basic concepts and symbols of graph coloring,the concepts of 2-dynamic coloring,r-dynamic coloring and list r-dynamic coloring as well as the research,and gives the main conclusions of this paper.At the end of the chapter,we provide about 3-grids,n-grids under specific conditions by means of vertex-to-vertex induction hypothesis and classification discussion and the main conclusions of the 3-dynamic chromatic number of the 1-planar graph.The Chapter 2 proves the four classification results of 3-grids with r=5 and r=6 respectively and the main results n-grids of r=2n and r=2n-1 on the basis of 2-grids by using the Squeeze theorem and Inductive Reasoning.The chapter 3 proves the upper bound of the 3-dynamic chromatic number of the 1-planar graph no exceeded 15 through Euler's formula,Minimal counterexample method and Weight transfer rule.The chapter 4 summarizes the defects of the main research results of this paper,and makes a prospect for these problems.There are 11 pictures and 82 references in this paper.