Injective coloring of some subclasses of bipartite graphs and chordal graphs

A vertex coloring of a graph G = (V, E) that uses k colors is called an injective k-coloring of G if no two vertices having a common neighbor have the same color. The minimum k for which G has an injective k-coloring is called the injective chromatic number of G. Given a graph G and a positive integer k, the DECIDE INJECTIVE COLORING PROBLEM iS to decide whether G admits an injective k-coloring. It is known that DECIDE INJECTIVE COLORING PROBLEM is NP-complete for bipartite graphs. In this paper, we strengthen this result by showing that this problem remains NP-complete for perfect elimination bipartite graphs, star-convex bipartite graphs and comb-convex bipartite graphs, which are proper subclasses of bipartite graphs. Moreover, we show that for every epsilon > 0, it is not possible to efficiently approximate the injective chromatic number of a perfect elimination bipartite graph within a factor of n(1/3-epsilon) unless ZPP = NP. On the positive side, we propose a linear time algorithm for biconvex bipartite graphs and O(nm) time algorithm for convex bipartite graphs for finding the optimal injective coloring. We prove that the injective chromatic number of a chordal bipartite graph can be determined in polynomial time. It is known that DECIDE INJECTIVE COLORING PROBLEM is NP-complete for chordal graphs. We give a linear time algorithm for computing the injective chromatic number of proper interval graphs, which is a proper subclass of chordal graphs. DECIDE INJECTIVE COLORING PROBLEM is also known to be NP-complete for split graphs. We show that DECIDE INJECTIVE COLORING PROBLEM remains NP-complete for K-1,K-t-free split graphs for t >= 4 and polynomially solvable for t <= 3. (C) 2020 Elsevier B.V. All rights reserved.