Name
Abstract | ||
|---|---|---|
Given an n-vertex graph G and two positive integers d,k ∈ ℕ, 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 u003e 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 ((lfloor2n/3rfloor,2n))-differential coloring problem, even in the case where the input graph is planar. |
Year | Venue | DocType |
|---|---|---|
2014 | J. Discrete Algorithms | Journal |
Volume | Citations | PageRank |
45 | 0 | 0.34 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael A. Bekos | 1 | 5 | 0.77 |
| Stephen G. Kobourov | 2 | 1440 | 122.20 |
| Michael Kaufmann 0001 | 3 | 41 | 8.28 |
| Sankar Veeramoni | 4 | 22 | 3.91 |