TY - GEN
T1 - The maximum k-differential coloring problem
AU - Bekos, Michael A.
AU - Kaufmann, Michael
AU - Kobourov, Stephen
AU - Veeramoni, Sankar
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
PY - 2015
Y1 - 2015
N2 - Given an n-vertex graph G and two positive integers d, k ∈ 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 (⌊2n/3⌋, 2n)-differential coloring problem, even in the case where the input graph is planar.
AB - Given an n-vertex graph G and two positive integers d, k ∈ 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 (⌊2n/3⌋, 2n)-differential coloring problem, even in the case where the input graph is planar.
UR - http://www.scopus.com/inward/record.url?scp=84922051449&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84922051449&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-46078-8_10
DO - 10.1007/978-3-662-46078-8_10
M3 - Conference contribution
AN - SCOPUS:84922051449
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 115
EP - 127
BT - SOFSEM 2015
A2 - Italiano, Giuseppe F.
A2 - Margaria-Steffen, Tiziana
A2 - Pokorný, Jaroslav
A2 - Quisquater, Jean-Jacques
A2 - Wattenhofer, Roger
PB - Springer-Verlag
T2 - 41st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2015
Y2 - 24 January 2015 through 29 January 2015
ER -