Injective chromatic number and chromatic number of the square of graphs
Seog‐Jin Kim · 2009
The injective chromatic number of a graph G is the minimum number of colors needed in order to color vertices of G so that two vertices with a common neighbor receive distinct colors. We prove that the injective chromatic number of G is at least the half of the chromatic number of G 2 , the square of G. This inequality is tight. An injective k-coloring of a graph G is an assignment of at most k colors to the vertices of G such that two vertices sharing a common neighbor must have distinct colors. The injective chromatic number i(G) of a graph G is the minimum k such that G has an injective k-coloring. This notion was