Coloring of Graphs Avoiding Bicolored Paths of a Fixed Length

Kırtışoğlu A., ÖZKAHYA L.

Graphs and Combinatorics, vol.40, no.1, 2024 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 40 Issue: 1
  • Publication Date: 2024
  • Doi Number: 10.1007/s00373-023-02739-4
  • Journal Name: Graphs and Combinatorics
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, MathSciNet, zbMATH, Civil Engineering Abstracts
  • Keywords: Acyclic coloring, Bicolored path, Cartesian products of graphs, Star coloring
  • Hacettepe University Affiliated: Yes


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.