Exact and Parameterized Algorithms for ( k , i )-Coloring

Graph coloring problem asks to assign a color to every vertex such that adjacent vertices get different color. There have been different ways to generalize classical graph coloring problem. Among them, we study (k, i)-coloring of a graph. In (k, i)-coloring, every vertex is assigned a set of k colors so that adjacent vertices share at most i colors between them. The (k, i)-chromatic number of a graph is the minimum number of total colors used to assign a proper (k, i)-coloring. It is clear that (1, 0)-coloring is equivalent to the classical graph coloring problem. We extend the study of exact and parameterized algorithms for classical graph coloring problem to (k, i)-coloring of graphs. Given a graph with n vertices and m edges, we design algorithms that take \(\mathcal {O}(2^{kn}\cdot n^{{\mathcal O}(1)})\) time to determine the (k, 0)-chromatic number. \(\mathcal {O}(4^n \cdot n^{{\mathcal O}(1)})\) time to determine the (k, k-1)-chromatic number. \(\mathcal {O}(2^{kn}\cdot k^{im} \cdot n^{{\mathcal O}(1)})\) time to determine the (k, i)-chromatic number.