Mixed Graph Colorings: A Historical Review

Mathematics

YuriN. Sotskov¹ 

[1] United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street 6, 220012 Minsk, Belarus;

关键词: mixed graph;    vertex coloring;    chromatic number;    edge coloring;    chromatic index;    chromatic polynomial;    unit-time scheduling;    makespan criterion;   

DOI  :  10.3390/math8030385

来源: DOAJ

【 摘 要 】

This paper presents a historical review and recent developments in mixed graph colorings in the light of scheduling problems with the makespan criterion. A mixed graph contains both a set of arcs and a set of edges. Two types of colorings of the vertices of the mixed graph and one coloring of the arcs and edges of the mixed graph have been considered in the literature. The unit-time scheduling problem with the makespan criterion may be interpreted as an optimal coloring of the vertices of a mixed graph, where the number of used colors is minimum. Complexity results for optimal colorings of the mixed graph are systematized. The published algorithms for finding optimal mixed graph colorings are briefly surveyed. Two new colorings of a mixed graph are introduced.

【 授权许可】

Unknown