Improper 2-colorings Of Planar Graphs Without 4-cycles And 6-cycles

The theory of graph coloring is the core of the study of graph theory,including vertex coloring,edge coloring,improper coloring and so on.In real life,the storage problem,the scheduling problem and the scheduling problem can all be transformed into the graph coloring theory to effectively solve.The definition of a graph's colouring:Let G=?V,E?is a graph,k?N⁺,and a function f:V?{1,2,···,k}.We call a graph G is a proper colouring of vertex if f?u??f?u? for ???uv?E.If V?G?can be partitioned into V₁,V₂,...,V_k,a graph G is k-colorable if-f V₁,V₂,...,V_kis independent set.If the requirement is relaxed,we have conception of improper coloring of graph.Let d₁,d₂,...,d_kbe k non-negative integers.A graph G is?d₁,d₂,...,d_k?-colorable,if the vertex set of G can be partitioned into subsets V₁,V₂,...,V_ksuch that the subgraph G[V_i]induced by V_ihas maximum degree at most d_ifor i=1,2,...,k.There are many good results in the improper coloring of bicyclic graphs.In this thesis,We mainly study the?d₁,d₂?-colorable problem.We have the following conclu-sions:?i?If G is planar graphs without 4-cycles and 6-cycles,then G is?4,4?-colorable.?ii?If G is planar graphs without 4-cycles and 6-cycles,then G is?3,5?-colorable.