Dot Shade Problem For Graphs Under Constraints

The coloring problem and the chromatic number problem are very active research topics in graph theory.In a nutshell,the colorings of a graph refer to coloring the vertices,edges or faces in the graph according to certain rules and classifying them by different colors.As a simple and intuitive way of expression in classification methods,graph coloring is widely used in various fields.The classic vertex(edge)coloring is to decompose the vertex(edge)set of the graph into the union of several independent sets of disjoint vertices(edges).Thus,people began to consider whether vertices(edges)could be decomposed into other forms.Naturally,people first thought of trees.In a tree,any two vertices are connected by a unique path.When people began to consider whether vertex(edge)set could be decomposed into trees,the idea of arboricity was born.If one considers the vertex decomposition,the concept of vertex arboricity arises.This dissertation mainly studies the vertex arboricity of graphs under several types of constraints.We stipulate that the graphs considered in this dissertation are limited and undirected simple graphs except as specifically indicated.The vertex arboricity of a graph G,denoted as va(G),is the minimum number of colors the vertices of the graph G can be colored so that every color class induces an acyclic subgraph of the graph G.The definition of vertex arboricity was first introduced by Chartrand et al.in 1968.In the next year,they proved that the vertex arboricity va(G)?(1+?(G))/2]for any graph G,and the vertex arboricity of a planar graph is at most the value 3.Subsequently,many scholars conducted research on the above-mentioned related issues and achieved a series of results.In 1979,Garey et al.showed that determining the vertex arboricity of a graph is an NP-hard problem.Specifically,this dissertation is divided into four chapters for discussion.The first chapter mainly introduces the basic terms,related definitions and symbols involved in this dissertation,and summarizes the current research status of the vertex arboricity.In addition,the main proof ideas used in this dissertation and the main results presented in this dissertation are briefly described in this first chapter.The second chapter mainly studies the vertex arboricity problem of the planar graph under restricted conditions,which proves that for the planar graph G,if no 3-cycle intersects a 4-cycle or no 3-cycle intersects a 5-cycle,then the vertex arboricity is at most the value 2.These results extend and improve some existing results.The third chapter mainly studies the vertex arboricity of the graph which can be embedded in a surface ? of non-negative Euler characteristic under the restricted conditions,which proves that for the graph G which can be embedded in a surface ? of non-negative Euler characteristic if no 3-cycle intersects a 5-cycle,or no 5-cycle intersects a 6-cycle,then the vertex arboricity is at most the value 2 in addition to the 4-regular quadrilateral mesh.In the fourth chapter,we have made some prospects for the vertex arboricity of the graph.