Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
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 complexit...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2015-03-01
|
| Series: | Archives of Control Sciences |
| Subjects: | |
| Online Access: | http://www.degruyter.com/view/j/acsc.2015.25.issue-1/acsc-2015-0007/acsc-2015-0007.xml?format=INT |