Star Coloring And Acyclic Coloring Of Several Graphs

A star coloring of G is a proper coloring of G such that the induced subgraphs of the vertices colored by any two colors do not contain the path on four vertices.The star chromatic number of G,denoted by _s(G),is the minimum number of colors used in star coloring of G.A acyclic coloring of G is a proper coloring of G such that the induced subgraphs of the vertices colored by any two colors do not contain the cycle.The acyclic chromatic number of G,denoted by a(G),is the minimum number of colors used in acyclic coloring of G.This paper mainly studies the star coloring and acyclic coloring of simple finite and undirected graphs,the specific content includes four parts:1.The star coloring of special regular bipartite graphs and their complements,special Mycielski’s graphs,double graphs and the generalized coronal product of any graph and disjoint graph sequence are studied,and the corresponding star chromatic numbers are obtained.2.The concept of colorful neighbor star coloring is introduced,and on this basis,the reachable upper bound of the star chromatic number of the generalized lexicographic product of any graph with colorful neighbor star coloring and the sequence of disjoin-t graphs is obtained.The exact values of the star chromatic number of some special generalized lexicographic products are obtained.3.The acyclic chromatic number of Mycielski’s graphs of some basic simple graphs and the generalized coronal product of any graph and disjoint graph sequence are obtained4.The concept of colorful neighbor acyclic coloring is introduced,and on this basis,the reachable upper bound of acyclic chromatic number of the generalized lexicographic product of any graph with colorful neighbor acyclic coloring and the sequence of disjoint graphs is obtained.The exact values of the acyclic chromatic number of some special generalized lexicographic products are obtained.