Given an n-vertex graph Gand two positive integers d, k is an element of N, the (d, kn)-differential coloring problem asks for a coloring of the vertices of G(if one exists) with distinct numbers from 1 to kn(treated as colors), such that the minimum difference between the two colors of any adjacent vertices is at least d. While it was known that the problem of determining whether a general graph is (2, n)-differential colorable is NP-complete, our main contribution is a complete characterization of bipartite, planar and outerplanar graphs that admit (2, n)-differential colorings. For practical reasons, we also consider color ranges larger than n, i.e., k > 1. We show that it is NP-complete to determine whether a graph admits a (3, 2n)-differential coloring. The same negative result holds for the (left perpendicular 2n/3 right pendicular, 2n)-differential coloring problem, even in the case where the input graph is planar.
| Identifer | oai:union.ndltd.org:arizona.edu/oai:arizona.openrepository.com:10150/626126 |
| Date | 07 1900 |
| Creators | Bekos, Michael A., Kaufmann, Michael, Kobourov, Stephen G., Stavropoulos, Konstantinos, Veeramoni, Sankar |
| Contributors | Department of Computer Science – University of Arizona, Tucson AZ, USA |
| Publisher | ELSEVIER SCIENCE BV |
| Source Sets | University of Arizona |
| Language | English |
| Detected Language | English |
| Type | Article |
| Rights | © 2017 Elsevier B.V. All rights reserved. |
| Relation | http://linkinghub.elsevier.com/retrieve/pii/S1570866717300503 |
Page generated in 0.0023 seconds