On the complexity of injective colorings and its generalizations

In this paper, we consider the complexity and algorithms of the injective coloring problem. We prove that it is NP-complete to determine the injective chromatic number even restricted to some special bipartite graphs. Furthermore, we show that for every ϵ>0, it is impossible to efficiently approximate the injective chromatic number of any bipartite graph within a factor of n13−ϵ unless ZPP=NP. For the max-injective coloring problem, we prove that there is a constant approximation algorithm on power chordal graphs with bounded injective chromatic number. We also devise a constant approximation algorithm for max-injective coloring some bipartite graphs. For the on-line injective coloring problem, we prove that First Fit (FF) injectively colors P3-free graphs perfectly, where First Fit is an on-line algorithm that simply assigns the smallest available color to each vertex. We also prove that the number of colors used by FF∗ for bipartite graph G is bounded by 32 times the on-line injective chromatic number, where FF∗ is an on-line algorithm equivalent to FF proper coloring the complement of G. Moreover, we present an improved algorithm BFF, and prove that it is optimal for on-line injectively coloring bipartite graphs.