Originators: G. Wegner; Geňa Hahn, André Raspaud, and Weifan
Wang (presented by Douglas West - REGS 2007) Definitions: A
k-coloring of the vertices of a graph is an injective coloring
if for every vertex v, the neighbors of v receive distinct
colors. The injective chromatic number χi(G) is the least k such
that G has an injective k-coloring. The square of a graph G is
the graph G² with the same vertex set as G in which vertices are
adjacent if their distance in G is at most 2 The maximum average
degree mad(G) of a graph G is the maximum, over all subgraphs,
of the average vertex degree. Background: An injective coloring
need not be a proper coloring; indeed, the injective chromatic
number of the Petersen graph is 5, with each color class
inducing K2. Hahn-Kratochvil-Siran-Sotteau [HKSS] introduced
χi(G) and noted for a graph with maximum degree d that d ≤ χi(G)
≤ χ(G²)≤ d²-d+1. Indeed, χi(G) equals the chromatic number of
the "common neighbor graph", the graph on vertex set V(G) where
vertices are adjacent if