Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

• Autorzy: Furmańczyk H. , Kubale M.

Identyfikatory

DOI

10.1515/acsc-2015-0007

• Języki publikacji: EN

Abstrakty

EN

In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP-complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan.

Słowa kluczowe

EN

batch scheduling; equitable coloring; semi-equitable coloring; cubic graph

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2015
• Tom: Vol. 25, no. 1
• Strony: 109--116
• Opis fizyczny: Bibliogr. 8 poz., rys., tab., wzory

Twórcy

autor

Furmańczyk H.

• Institute of Informatics, University of Gda´nsk, Wita Stwosza 57, 80-952 Gda´nsk, Poland

autor

Kubale M.

• Department of Algorithms and System Modeling, Technical University of Gda´nsk, Narutowicza 11/12, 80-233 Gda´nsk, Poland

Bibliografia

• [1] B.-L. Chen, K. W. Lih and P. L. Wu: Equitable coloring and the maximum degree.European J. of Combinatorics, 15 (1994), 443-447.
• [2] A. Frieze and S. Suen: On the independence number of random cubic graphs. Random Graphs and Structures, 5 (1994), 649-664.
• [3] H. Furmańczyk and M. Kubale: Equitable coloring of corona products of cubic graphs is harder than ordinary coloring. [arXiv:1409.0650].
• [4] H. Furmańczyk, M. Kubale and S. P. Radziszowski: On bipartization of cubic graphs by removal of an independent set. [arXiv:1406.2728v2].
• [5] H. Furmańczyk and M. Kubale: Batch processing of unit-length jobs with cubic incompatibility graphs on three uniform machines. [arXiv:1502.04240].
• [6] M. R. Garey, D. S. Johnson and L. Stockmeyer: Some simplified NPcomplete problems. Theoretical Computer Science 1 (1976), 237-267.
• [7] W. Meyer: Equitable coloring. The American Mathematical Monthly, 80 (1973), 920-922.
• [8] S. Skulrattanakulchai: Δ-list vertex coloring in linear time. 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, (2002), 240-248.

Uwagi

EN

This article was partially supported by the Narodowe Centrum Nauki under grant DEC-2011/02/A/ST6/00201.