R-dynamic Coloring Of Planar Graphs Without Cycles Of Specific Lengths

All graphs are finite simple graphs in this paper.For a graph G,we use V(G),E(G),F(G),Δ(G),δ(G),and g(G)to denote the vertex set,edge set,face set,maximum degree,minimum degree and girth,respectively.A graph G is Planar if it can be embedded in a plane and its edges intersect only at its endpoints.A planar graph is called a planar graph if it can be embedded in a plane.The vertices and edges of a plane graph G divide the whole plane into connected regions whose closures are called planes of the plane graph.Let k,r be positive integers,a(k,r)-dynamic coloring(abbreviated as(k,r)-coloring)of graph G is a mapping φ:V(G)→｛1,2,…,k} satisfying both the following:(1)φ(u)≠φ(v)for every edge uv∈E(G);(2)|φ(NG(v))|≥ min{dG(v),r} for any v∈V(G).For a fixed integer r>0,the r-dynamic chromatic number of G,denoted by χr(G),is the smallest integer k such that G has an r-dynamic coloring.In 2001,Montgomery proposed the concept of dynamic coloring for the first time.In 2011,Lai Hong jian et al.proposed a conjecture about r-hued coloring of planar graphs:For planar graphs G,if 1≤r≤3,then χr(G)≤r+3;If 3≤r≤7,then χr(G)≤r+5;If r≥8,then χr(G)≤[3r/2]+1.According this conjecture,many scholars at home and abroad have carried out research,but this conjecture is still open.This dissertation studies some conclusions about r-dynamic coloring of planar graphs with girth or without cycles of specific lengths.In the first chapter,we introduced some basic concepts of graph theory and research status of r-dynamic coloring.In the second chapter,we study the plane graph G without adjacent 5-cycles and 5-cycles,if r≥11,g(G)≥5,then χr(G)≤r+4.In the third chapter,we study the plane graph G without 3,5-cycles,and without adjacent 4-cycles and 7--cycles,if r≥13,then χr(G)≤r+3;the plane graph G without 4,5-cycles,and without intersecting 3-cycles,if r≥14,then χr(G)≤r+3.In the fourth chapter,we conclude this paper and proposed research problems.