Dynamic Coloring Of Some Topological Graphs

A graph is k-planar if it can be drawn in the plane so that each edge is crossed at most k times.Typically,the class of 1-planar graphs is among the most investigated graph families within the so-called "beyond planar graphs”.An outer 1-planar graph is a graph admitting a drawing in the plane so that all vertices appear in the outer region of the drawing and every edge crosses at most one other edge.A proper l-coloring of a graph G is a coloring on V(G)using l colors so that adjacent vertices receive distinct colors.If every vertex of degree at least two is incident with at least two colors,we call this proper l-coloring a dynamic lcoloring.An r-dynamic l-coloring of a graph G is a proper l-coloring such that for any vertex v,there are at least min?r,d(v)} distinct colors appearing on the neighbors of v.The(list)dynamic coloring,an important research direction in graph theory and theoretical computer science,can be used to solve some critical problems on the channel assignment problem.In this paper,We mainly prove the following conclusions.First of all,the dynamic coloring and list dynamic coloring of 1-planar graphs are studied for the first time in this paper,in chapter 2,we show that the list dynamic chromatic number of every 1-planar graph is at most 11.Moreover,we show a relationship between the dynamic coloring of 1planar graphs and the proper coloring of 2-planar graphs,which states that the dynamic(list)chromatic number of the class of 1-planar graphs is at least the(list)chromatic number of the class of 2-planar graphs.Secondly,in chapter 3,Kim and Park(2011)announced that the list dynamic chromatic number of every graph with maximum average degree less than 8/3 is at most 4.However,this result is incorrect since the cycle C5 on five vertices has maximum average degree 2 and list dynamic chromatic number 5.In this paper,we correct this flaw by proving that the list dynamic chromatic number of every graph with maximum average degree less than 8/3 is at most 4(being sharp)if it is a normal graph,which is a graph having no component isomorphic to C5.Meanwhile,we prove that every series-parallel graph has list dynamic chromatic number at most 4 if it is a normal graph,and exactly 5 otherwise,which improves a result of Song et al.(2014)that states that the list dynamic chromatic number of every series-parallel graph is at most 6.At last,in chapter 4,we conclude that every(resp.maximal)outer 1-planar graph of minimum degree at least 2 has an edge with the sum of the degrees of its two end-vertices being at most 9(resp.7),and this upper bound is sharp.On the other hand,we show that the list 3-dynamic chromatic number of every outer 1-planar graph is at most 6,and this upper bound is best possible.