INJECTIVE COLORING OF CENTRAL GRAPHS

INJECTIVE COLORING OF CENTRAL GRAPHS

S. S. Mirdamad, D. A. Mojdeh

[PDF]

Abstract

For a given graph G = (V (G),E(G)), researchers have introduced different colorings based on the distances of the vertices. An injective coloring of a graph G is an assignment of colors to the vertices of G such that no two vertices with a common neighbor receive the same color. The injective chromatic number of G, denoted by χi(G), is the minimum number of colors required for an injective coloring of G. The concept of a central graph of any graph has been a widely studied topic among mathematical researchers and graph theorists nowadays. The central graph of a given graph G, denoted by C(G), is the graph obtained by subdividing each edge of G exactly once and also adding an edge between each pair of non-adjacent vertices of G. In this work, we present some results on injective coloring of central graph C(G) of G. We show that for a graph G of order n and maximum degree Δ(G), n − 1 ≤ χi(C(G)) ≤ n2 − 3n − (n − 3)Δ(G) + 3. Next, we will closely examine the injective chromatic number of the central graph of some special graphs and trees. Finally, for any graph H, and the corona product (H ◦ K1), (H ◦ K2), we will have a precise determination of the injective chromatic number of C(H ◦ K1) and C(H ◦ K2) in terms of χi(C(H)) and order of H.

Keywords

Graph coloring, injective coloring, central graphs, corona product.