This paper examines a parameterized problem that we refer to as n - k GRAPH COLORING, i.e., the problem of determining whether a graph G with n vertices can be colored using n - k colors. As the main result of this paper, we show that there exists a O(kn 2  + k 2  + 2 3.8161k ) = O(n 2 ) algorithm for n - k GRAPH COLORING for each fixed k. The core technique behind this new parameterized algorithm is kernalization via maximum (and certain maximal) matchings. The core technical content of this paper is a near linear-time kernelization algorithm for n-k CLIQUE COVERING. The near linear-time kernelization algorithm that we present for n - k CLIQUE COVERING produces a linear size (3k - 3) kernel in O(k(n + m)) steps on graphs with n vertices and m edges. The algorithm takes an instance (G, k) of CLIQUE COVERING that asks whether a graph G can be covered using |V| - k cliques and reduces it to the problem of determining whether a graph G' = (V',E') of size < 3k - 3 can be covered using |V'|-k' cliques. We also present a similar near linear-time algorithm that produces a 3k kernel for VERTEX COVER. This second kernelization algorithm is the crown reduction rule.
['Benny Chor', 'Michael R. Fellows', 'David W. Juedes']
Linear kernels in linear time, or how to save k colors in O(n2) steps