Mixed Graph Colorings: A Historical Review
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 ar...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/3/385 |
| _version_ | 1819276832542818304 |
|---|---|
| author | Yuri N. Sotskov |
| author_facet | Yuri N. Sotskov |
| author_sort | Yuri N. Sotskov |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-23T23:46:29Z |
| format | Article |
| id | doaj.art-d65a28d7ad7e46c8a14781e60f0dc5fd |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-12-23T23:46:29Z |
| publishDate | 2020-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-d65a28d7ad7e46c8a14781e60f0dc5fd2022-12-21T17:25:29ZengMDPI AGMathematics2227-73902020-03-018338510.3390/math8030385math8030385Mixed Graph Colorings: A Historical ReviewYuri N. Sotskov0United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova Street 6, 220012 Minsk, BelarusThis 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.https://www.mdpi.com/2227-7390/8/3/385mixed graphvertex coloringchromatic numberedge coloringchromatic indexchromatic polynomialunit-time schedulingmakespan criterion |
| spellingShingle | Yuri N. Sotskov Mixed Graph Colorings: A Historical Review Mathematics mixed graph vertex coloring chromatic number edge coloring chromatic index chromatic polynomial unit-time scheduling makespan criterion |
| title | Mixed Graph Colorings: A Historical Review |
| title_full | Mixed Graph Colorings: A Historical Review |
| title_fullStr | Mixed Graph Colorings: A Historical Review |
| title_full_unstemmed | Mixed Graph Colorings: A Historical Review |
| title_short | Mixed Graph Colorings: A Historical Review |
| title_sort | mixed graph colorings a historical review |
| topic | mixed graph vertex coloring chromatic number edge coloring chromatic index chromatic polynomial unit-time scheduling makespan criterion |
| url | https://www.mdpi.com/2227-7390/8/3/385 |
| work_keys_str_mv | AT yurinsotskov mixedgraphcoloringsahistoricalreview |