2023/05/29 by Choudhary, Harshit Kumar, Reddy, I. Vinod
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2305.17956
A star coloring of a graph G is a proper vertex-coloring such that no path on four vertices is 2-colored. The minimum number of colors required to obtain a star coloring of a graph G is called star chromatic number and it is denoted by χs(G). A graph G is called k-critical if χs(G)=k and χs(G -e) < χs(G) for every edge e ∈ E(G). In this paper, we give a characterization of 3-critical, (n-1)-critical and (n-2)-critical graphs with respect to star coloring, where n denotes the number of vertices of G. We also give upper and lower bounds on the minimum number of edges in (n-1)-critical and (n-2)-critical graphs.