On maximum differential graph coloring

Yifan Hu; Stephen Kobourov; Sankar Veeramoni

doi:10.1007/978-3-642-18469-7_25

On maximum differential graph coloring

Yifan Hu, Stephen Kobourov, Sankar Veeramoni

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Scopus citations

Abstract

We study the maximum differential graph coloring problem, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of k-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs.

Original language	English (US)
Title of host publication	Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers
Pages	274-286
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-18469-7_25
State	Published - 2011
Event	18th International Symposium on Graph Drawing, GD 2010 - Konstanz, Germany Duration: Sep 21 2010 → Sep 24 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6502 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	18th International Symposium on Graph Drawing, GD 2010
Country/Territory	Germany
City	Konstanz
Period	9/21/10 → 9/24/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-18469-7_25

Cite this

Hu, Y., Kobourov, S., & Veeramoni, S. (2011). On maximum differential graph coloring. In Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers (pp. 274-286). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6502 LNCS). https://doi.org/10.1007/978-3-642-18469-7_25

On maximum differential graph coloring. / Hu, Yifan; Kobourov, Stephen; Veeramoni, Sankar.
Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers. 2011. p. 274-286 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6502 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hu, Y, Kobourov, S & Veeramoni, S 2011, On maximum differential graph coloring. in Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6502 LNCS, pp. 274-286, 18th International Symposium on Graph Drawing, GD 2010, Konstanz, Germany, 9/21/10. https://doi.org/10.1007/978-3-642-18469-7_25

@inproceedings{8a7f68c6e53d4787b02eb5dec27c5bf9,

title = "On maximum differential graph coloring",

abstract = "We study the maximum differential graph coloring problem, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of k-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs.",

author = "Yifan Hu and Stephen Kobourov and Sankar Veeramoni",

year = "2011",

doi = "10.1007/978-3-642-18469-7_25",

language = "English (US)",

isbn = "9783642184680",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "274--286",

booktitle = "Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers",

note = "18th International Symposium on Graph Drawing, GD 2010 ; Conference date: 21-09-2010 Through 24-09-2010",

}

TY - GEN

T1 - On maximum differential graph coloring

AU - Hu, Yifan

AU - Kobourov, Stephen

AU - Veeramoni, Sankar

PY - 2011

Y1 - 2011

N2 - We study the maximum differential graph coloring problem, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of k-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs.

AB - We study the maximum differential graph coloring problem, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of k-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs.

UR - http://www.scopus.com/inward/record.url?scp=79952264539&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79952264539&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18469-7_25

DO - 10.1007/978-3-642-18469-7_25

M3 - Conference contribution

AN - SCOPUS:79952264539

SN - 9783642184680

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 274

EP - 286

BT - Graph Drawing - 18th International Symposium, GD 2010, Revised Selected Papers

T2 - 18th International Symposium on Graph Drawing, GD 2010

Y2 - 21 September 2010 through 24 September 2010

ER -

On maximum differential graph coloring

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this