A Square Chromatic Number of Some Graph Classes

Abstract

Let G be a graph with vertex set V(G). A square vertex coloring of a graph G is defined as a function w : V(G) → {1, 2, . . . , k}, where k ∈ Z⁺, such that any two vertices of G whose distance is at most two are assigned different colors. A square-k coloring of G is a square coloring that uses k colors. The minimum number of colors required in a square vertex coloring of G is called the square chromatic number, denoted by χ_p(G). The value of the square chromatic number of a graph depends on its structural properties. This article investigates the square chromatic number of graphs by examining several classes of graphs, namely complete graphs, bipartite graphs, cycle graphs, caterpillar graphs, wheel graphs, trees, and complete block path graphs.

Keywords: square vertex coloring, square chromatic number, complete graph, complete bipar- tite graph, cycle, caterpillar graph, wheel graph, tree, complete block path graph.