A Square Chromatic Number of Some Graph Classes

Abstract

Let G is a simple and connected graph. For two distinct vertices u,v ∈ V(G), the distance from vertex u to vertex v in G is denoted by d(u,v). A square coloring of G is the function: w : V(G) → {1, 2, …, k}, k ∈ Z⁺, such that w(u) ≠ w(v) for any two distinct vertices u,v with d(u,v) ≤ 2. The minimum number of colors required by a square coloring is called the square chromatic number of G, denoted by χ_p(G), is the minimum positive integer k such that admits a square k-coloring of G using k distinct colors. This study explains the exact value of the square chromatic number of several graph classes, namely complete graphs, bipartite graphs, complete bipartite graphs, cycles, trees, caterpillar graphs, wheel graphs, and complete block path graphs.