The Conditional Chromatic Number Of Generalized Petersen Graphs

The study on graph colorings plays a central role in graph theory and be widely used inscheduling problem, sequencing problem, resource allocation,signal frequency assignmentproblems, transportation arrangement, circuit design and storage problems and so on which arerelated to the solution of practical problems on the task allocation. The condition chromaticnumber of a graph is a generalization of classic chromatic number. It is NP-complete todetermine condition chromatic numbers of graphs. The conditional coloring of the generalizedPetersen graphs has been studied and has the following conclusions.Zhong Yun proved the upperbound of the3-condition chromatic number of the generalized Petersen graph is8, and Chen HuaZhu improved the upper bound and proved it is7.This paper further studies the conditionalcoloring of the generalized Petersen graphs.In this paper, we proved that the lower bound of the3-condition chromatic number of thegeneralized Petersen graph is4, and this generalized Petersen graph is characterized.We alsoimproved the upper bound of the generalized Petersen graphs.We prove if a graph G is a generalized Petersen graph P (n, t), but it isn’t Petersengraph P (5,2),then...