Variations of Star Coloring on Graphs

Abstract

This thesis is constructed on a variety of coloring types in five chapters. Following the Introduction chapter, elementary definitions and methods used throughout the work are presented in Chapter 2. Chapter 3 presents some results on acyclic and star colorings that forbid bicolored copies of cycles and paths on four vertices, respectively. Non-repetitive and $k$-distance colorings are closely related to the star coloring, and these colorings are also presented here to provide a perspective on the star coloring. $P_k$-coloring is a proper coloring with no bicolored paths with $k$ vertices. Chapter 4 is devoted to products of graphs, in particular, cylinder, 2-dimensional grid, and 2-dimensional tori that are the variations of products of paths and cycles. We find exact values of $P_k$-chromatic numbers of these graph families for $k=5,6$. The probabilistic method is a fundamental tool to show that the desired object exists with a positive probability under random construction. In Chapter 5, we provide general bounds on the $P_k$-coloring. Moreover, we obtain similar bounds considering colorings with no bicolored cycles.