Edge Coloring Of Signed Generalized Petersen Graphs

The graph coloring originated from the famous four-color problem and later developed into an important branch of graph theory.The study of the four-color problem promoted the development of graph theory.Scholars gave some concepts about graph coloring such as vertex coloring,edge coloring and list coloring.There are a series of results about graph coloring.In 1953,Harry introduced the definition of signed graphs.In 2020,Behr and Zhang independently gave the definition of proper edge coloring of signed graphs,and these two definitions are equivalent.In recent years,the edge coloring of signed graphs has been a very popular research problem,and Petersen graph is a widely concerned graph,which is often used as examples or counterexamples in proofs.Generalized Petersen graphs are the generalization of Petersen graph,so in this paper,we mainly focus on the edge coloring of signed generalized Petersen graphs.We study properties of some perfect matchings of generalized Petersen graphs and the structure and properties of graphs obtained by deleting a perfect matching from signed generalized Petersen graphs,and we obtain some results about the edge coloring of signed generalized Petersen graphs.The framework of this paper is as follows:In the first chapter,we introduce the research background of simple graph coloring,signed simple graph coloring and generalized Petersen graph.In the second chapter,we introduce some basic definitions and notations of simple graphs and generalized Petersen graphs.Moreover,we introduce definitions,properties and related results of signed graph coloring that are used in this paper.For convenience,we give some new definitions and notations.In the third chapter,we firstly prove that when k=1,the chromatic index of signed generalized Petersen graph is 3.Next,when n ∈ {5,6},we discuss properties of matchings of GP(n,2).We also analyze properties of the graph obtained by deleting the matching from GP(n,2).Finally,we prove that except for some special cases,the chromatic index of GPσ(5,2)and GPσ(6,2)is 3.In the fourth chapter,when k=2,n=6p+3(p≥1)and n=2p(p≥ 4),we study the structure and properties of matchings of GP(n,2).Next,we also analyze the structure and properties of the graph obtained by deleting a matching from GP(n,2).We prove that when k=2,n=6p+3(p≥1)and n=2p(p≥4),the chromatic index of signed generalized Petersen graph GPσ(n,2)is 3.In the fifth chapter,we briefly summarize results obtained in this paper and give a summary of this paper.Moreover,we looking forward to the future research on edge coloring of signed generalized Petersen graphs.