Lexicographically First ∆ + 1 Vertex Coloring (LFDVC)

Input

An undirected graph $G = (V, E)$ with $\Delta$ equal to the maximum degree of any vertex in $V$, an ordering $v_1, \ldots, v_n$ on the vertices of $V$, a designated color $c$, and a vertex $v$.

Problem

Is vertex $v$ colored with color $c$ in the lexicographically least coloring of the vertices of $G$?

Definitions

A coloring is an assignment of colors to the vertices such that no adjacent vertices receive the same color. The coloring uses at most $\Delta + 1$ colors. If $c_i$ is the color of $v_i$, where $c_i \in \{1, \ldots, \Delta + 1\}$, then each coloring corresponds to a $(\Delta + 1)$-ary number, and the least coloring is well-defined.

Status

$\P$-complete (Luby [1]).

Remarks

The reduction to show hardness is from NANDCVP. The problem of $\Delta - 1$ coloring is $\NP$-complete (Garey and Johnson [2]). For graphs that are not an odd cycle or complete, a $\Delta$ coloring can be found in polynomial time (Brook’s Theorem, see Brooks [3] or, for example, Bondy and Murty [4]). However, this is not necessarily the lexicographically first coloring. $\Delta + 1$ vertex coloring is $\NC^1$ reducible to finding a maximal independent set, but the maximal independent set algorithm (Karp and Wigderson [5]) does not produce the lexicographically first maximal independent set.

It is possible to color a graph with $\Delta$ colors in $\NC$, although again the coloring produced is not the lexicographically first (Hajnal and Szemerédi [6], Karchmer and Naor [7], Karloff [8]). Chlebus et al. show that for tree structured graphs LFDVC can be solved in $\NC$ [9]. There are also $\NC$ algorithms for five coloring planar graphs (Boyar and Karloff [10], Naor [11]).

Karloff and Shmoys give $\NC$ algorithms for edge coloring problems [12]. In particular, they show that multigraphs can be edge colored with $3\lceil \Delta/2 \rceil$ colors on a COMMON CRCW-PRAM using $O((\log(\Delta|V|))^3)$ time and $\Delta|V|$ processors. For the same model and multigraphs with $\Delta$ equal to three, they use four colors, and $O(\log |V|)$ time and $|V| + |E|$ processors. Again on the same model for simple graphs using $\Delta + 1$ colors, Karloff and Shmoys obtain a $\Delta^{O(1)}(\log |V|)^{O(1)}$ time, $|V|^{O(1)}$ processor algorithm. This results in an $\NC$ algorithm for polylogarithmic $\Delta$. See also EC.