The Chromatic Numbers And Clique Numbers Of Orbital Graphs Of Induced Primitive Action Of Symmetric Group S_n Acting On Disordered R-Subset Of A Finite Set

Determining the chromatic numbers and clique numbers of graphs are two basic and important problems in graph theory.Although it is already known in theory that the prob-lem of determining chromatic numbers and clique numbers of general graphs is NP-hard,determining the chromatic numbers and clique numbers of certain special graphs with extra conditions is attracting much attention of mathematicians.The initial motivation of this work is to study primitive permutation groups which are synchronizing.Current-ly this is a frontier topic in the study of permutation group theory and algebraic graph theory.In 2008 Peter Neumann found out that there is a close relationship between the synchronization of general primitive groups and their orbital graphs,that is,by analyzing weather the chromatic number and the clique number are equal or not.This fact has since opened up a new window for researching synchronization of primitive permutation groups,namely from the perspective of graph theory to determine the chromatic numbers and clique numbers of the orbital graphs of primitive groups.When studying the synchronization of primitive permutation groups,one of the im-portant types is the type of almost simple primitive groups.Among them,the symmetric group S_n is one of the most typical type.In this thesis we study the chromatic number-s and clique numbers of orbital graphs of induced primitive action of symmetric group S_n acting on disordered r-subset of a finite set.We start from the definition of orbital graphs of induced primitive action that symmetric group S_n acts on disordered r-subset,then we reveal the connection between the orbital graphs and generalized Johnson graphs.By analyzing the properties of the generalized Johnson graphs we obtain the chromatic numbers and clique numbers(range)of the corresponding orbital graphs.In particular,we deal with the situations of r = 2,3,4,and promote it to the general situation.The chromatic numbers and clique numbers of a graph are crucial for the graph itself,and the chromatic number is a classification of the vertex set of a graph.So we have a relatively clear understanding for orbital graph of induced primitive action that symmetric group S_n acting on disordered r-subset.Finally,some relevant results will be used to determine the synchronization of symmetric group S_n acting on disorder r-subset of a finite set.