Linear-time algorithm for the edge-colorability of a graph with prescribed vertex types (Q1411559)

The following coloring problem is considered: Given a graph \(G = (V,E)\) and a partition \(V = V_c \dot\cup V_d \dot\cup V_0\) of the vertices, find a mapping \(\chi : E \to \mathbb N\) (called coloring) such that (a) each vertex from \(V_c\) is incident with at least two edges of the same color, and (b) each vertex from \(V_d\) is incident with at least two edges in different colors. There is no requirement for vertices from \(V_0\). Note that \(\chi\) needs not to be an edge-coloring in the usual sense (edges sharing a vertex have different colors), and cannot be, if \(V_c \neq \emptyset\). This problem is (apart from trivialities) the problem to color a mixed hypergraph in which every vertex is contained in exactly two hyperedges. See the second author's recent book [\textit{V. I. Voloshin}, Coloring mixed hypergraphs: theory, algorithms and applications (Fields Institute Monographs. 17. Providence, RI: American Mathematical Society (AMS)) (2002; Zbl 1001.05003)] for more on this topic. A linear-time algorithm solving this problem is given in the present paper. Thus this special case is different from the general problem of coloring mixed hypergraphs, which is NP-hard. There seems to be a slight mistake in the paper, as all colorings are defined to be injective mappings. This seems to make little sense if there are vertices in \(V_c\). If all `injective's in the paper are removed, however, everything seems fine.