Vertex Partition Of Sparse Graphs

Graph theory is a branch of mathematics and it takes graphs as research objects.Vertex partiton of graphs is a hot topic in graph theory research,and it has important theoreti-cal significance in graph theory.Vertex partition is also widely used in computer science,information science and many other fields.There have been many achievements on ver-tex partition of graphs.The famous four-color theorem is that every plane graph has an（I,I,I,I）-partiton,where I represents an independent set.The（k,j）-partiton of a sparse graph is to divide the graph into two parts,so that the maximum degree of the vertices in one part is at most k,and the maximum degree of the vertices in another part is at most j When the girth of a graph is at least 5,there will be an（I,F）-partiton of this graph,where F represents a forest.If the maximum average degree of a graph G is at most 12/5,there will be an（I,F₁）-partiton of G,where F₁ is a forest and the maximum degree of each vertex in the forest is at most one.Therefore,it is very meaningful to find one appropriate graph class and study its vertex partition.This thesis mainly studies the vertex partiton of sparse graphs,which is divided into four chapters.In Chapter One,we mainly introduces some definitions and terminology of this thesis,some researches on vertex partition at home and abroad,and the main methods used in this thesis.In Chapter Two,we prove that in a graph class satisfying certain conditions,if the maximum average degree of a graph is at most 8/3,then G admits an（I,O₃）-partition,where O₃ is a graph with order at most 3.In Chapter Three,we prove that in a graph class satisfying certain conditions,if the maximum average degree of a graph is at most 11/4,then G admits an（I,O₄）-partition,where O₄ is a graph with order at most 4.In Chapter Four,we make summary and prospect.