IMI/Publicaţii/CSJM/Ediţii/CSJM v.11, n.1 (31), 2003/

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

Authors: Zs. Tuza, V. Voloshin


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.

Z.Tuza, V.Voloshin,
Zsolt Tuza
Computer and Automation Institute
Hungarian Academy of Sciences
H-1111 Budapest, Kende u. 13-17, Hungary
Vitaly Voloshin
Institute of Mathematics and Computer Science
Moldovan Academy of Sciences
MD-2028 Chisinau, str. Academiei 5, Moldova


Adobe PDF document0.13 Mb