Mixed Graph Colorings: A Historical Review

Yuri N. Sotskov
Additional contact information
Yuri N. Sotskov: United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street 6, 220012 Minsk, Belarus

Mathematics, 2020, vol. 8, issue 3, 1-24

Abstract: 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.

Keywords: mixed graph; vertex coloring; chromatic number; edge coloring; chromatic index; chromatic polynomial; unit-time scheduling; makespan criterion (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/3/385/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/3/385/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:3:p:385-:d:330378

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().