Linear-time algorithm for the edge-colorability of a graph with prescribed vertex types
Źsolt Tuza, Vitaly Voloshin · DOAJ (DOAJ: Directory of Open Access Journals) · 2003
We consider the coloring of edges in a graph in which there are vertices of three types. In a feasible edge coloring, each vertex of the first type is incident with at least two edges of the same color, and each vertex of the second type with at least two edges of different colors; while no constraints are required for the vertices of the third type. We present a characterization of colorable graphs, and a linear-time algorithm to decide whether a given graph with prescribed vertex types admits a feasible edge coloring.