Akademik Veri Yönetim Sistemi
Graphs and Combinatorics, cilt.40, sa.1, 2024 (SCI-Expanded)
The problem of finding the minimum number of colors to color a graph properly without containing any bicolored copy of a fixed family of subgraphs has been widely studied. Most well-known examples are star coloring and acyclic coloring of graphs (Grünbaum in Isreal J Math 14(4):390–498, 1973) where bicolored copies of P4 and cycles are not allowed, respectively. In this paper, we introduce a variation of these problems and study proper coloring of graphs not containing a bicolored path of a fixed length and provide general bounds for all graphs. A Pk -coloring of an undirected graph G is a proper vertex coloring of G such that there is no bicolored copy of Pk in G, and the minimum number of colors needed for a Pk -coloring of G is called the Pk -chromatic number of G, denoted by sk(G). We provide bounds on sk(G) for all graphs, in particular, proving that for any graph G with maximum degree d≥ 2 , and k≥ 4 , sk(G)≤⌈610dk-1k-2⌉. Moreover, we find the exact values for the Pk -chromatic number of the products of some cycles and paths for k= 5 , 6.