The maximum k-differential coloring problem

Michael A. Bekos, Michael Kaufmann, Stephen G. Kobourov, Konstantinos Stavropoulos, Sankar Veeramoni

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)35-53
Number of pages19
JournalJournal of Discrete Algorithms
StatePublished - Jul 2017
Externally publishedYes


  • Differential chromatic number
  • Differential coloring
  • Maximum k-differential coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'The maximum k-differential coloring problem'. Together they form a unique fingerprint.

Cite this