Happy edges: Threshold-coloring of regular lattices

Md Jawaherul Alam; Stephen G. Kobourov; Sergey Pupyrev; Jackson Toeniskoetter

doi:10.1007/978-3-319-07890-8_3

Happy edges: Threshold-coloring of regular lattices

Md Jawaherul Alam, Stephen G. Kobourov, Sergey Pupyrev, Jackson Toeniskoetter

Computer Science

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

4 Scopus citations

Abstract

We study a graph coloring problem motivated by a fun Sudoku-style puzzle. Given a bipartition of the edges of a graph into near and far sets and an integer threshold t, a threshold-coloring of the graph is an assignment of integers to the vertices so that endpoints of near edges differ by t or less, while endpoints of far edges differ by more than t. We study threshold-coloring of tilings of the plane by regular polygons, known as Archimedean lattices, and their duals, the Laves lattices. We prove that some are threshold-colorable with constant number of colors for any edge labeling, some require an unbounded number of colors for specific labelings, and some are not threshold-colorable.

Original language	English (US)
Title of host publication	Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings
Publisher	Springer-Verlag
Pages	28-39
Number of pages	12
ISBN (Print)	9783319078892
DOIs	https://doi.org/10.1007/978-3-319-07890-8_3
State	Published - 2014
Event	7th International Conference on Fun with Algorithms, FUN 2014 - Sicily, Italy Duration: Jul 1 2014 → Jul 3 2014

Publication series

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

Other

Other	7th International Conference on Fun with Algorithms, FUN 2014
Country/Territory	Italy
City	Sicily
Period	7/1/14 → 7/3/14

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-07890-8_3

Cite this

Alam, M. J., Kobourov, S. G., Pupyrev, S., & Toeniskoetter, J. (2014). Happy edges: Threshold-coloring of regular lattices. In Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings (pp. 28-39). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8496 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-319-07890-8_3

Happy edges: Threshold-coloring of regular lattices. / Alam, Md Jawaherul; Kobourov, Stephen G.; Pupyrev, Sergey et al.
Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings. Springer-Verlag, 2014. p. 28-39 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8496 LNCS).

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

Alam, MJ, Kobourov, SG, Pupyrev, S & Toeniskoetter, J 2014, Happy edges: Threshold-coloring of regular lattices. in Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8496 LNCS, Springer-Verlag, pp. 28-39, 7th International Conference on Fun with Algorithms, FUN 2014, Sicily, Italy, 7/1/14. https://doi.org/10.1007/978-3-319-07890-8_3

Alam MJ, Kobourov SG, Pupyrev S, Toeniskoetter J. Happy edges: Threshold-coloring of regular lattices. In Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings. Springer-Verlag. 2014. p. 28-39. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-07890-8_3

@inproceedings{eef7992f9f744a268e3019a310f29eeb,

title = "Happy edges: Threshold-coloring of regular lattices",

abstract = "We study a graph coloring problem motivated by a fun Sudoku-style puzzle. Given a bipartition of the edges of a graph into near and far sets and an integer threshold t, a threshold-coloring of the graph is an assignment of integers to the vertices so that endpoints of near edges differ by t or less, while endpoints of far edges differ by more than t. We study threshold-coloring of tilings of the plane by regular polygons, known as Archimedean lattices, and their duals, the Laves lattices. We prove that some are threshold-colorable with constant number of colors for any edge labeling, some require an unbounded number of colors for specific labelings, and some are not threshold-colorable.",

author = "Alam, {Md Jawaherul} and Kobourov, {Stephen G.} and Sergey Pupyrev and Jackson Toeniskoetter",

note = "Funding Information: Supported in part by NSF grants CCF-1115971 and DEB 1053573.; 7th International Conference on Fun with Algorithms, FUN 2014 ; Conference date: 01-07-2014 Through 03-07-2014",

year = "2014",

doi = "10.1007/978-3-319-07890-8_3",

language = "English (US)",

isbn = "9783319078892",

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

publisher = "Springer-Verlag",

pages = "28--39",

booktitle = "Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings",

}

TY - GEN

T1 - Happy edges

T2 - 7th International Conference on Fun with Algorithms, FUN 2014

AU - Alam, Md Jawaherul

AU - Kobourov, Stephen G.

AU - Pupyrev, Sergey

AU - Toeniskoetter, Jackson

N1 - Funding Information: Supported in part by NSF grants CCF-1115971 and DEB 1053573.

PY - 2014

Y1 - 2014

N2 - We study a graph coloring problem motivated by a fun Sudoku-style puzzle. Given a bipartition of the edges of a graph into near and far sets and an integer threshold t, a threshold-coloring of the graph is an assignment of integers to the vertices so that endpoints of near edges differ by t or less, while endpoints of far edges differ by more than t. We study threshold-coloring of tilings of the plane by regular polygons, known as Archimedean lattices, and their duals, the Laves lattices. We prove that some are threshold-colorable with constant number of colors for any edge labeling, some require an unbounded number of colors for specific labelings, and some are not threshold-colorable.

AB - We study a graph coloring problem motivated by a fun Sudoku-style puzzle. Given a bipartition of the edges of a graph into near and far sets and an integer threshold t, a threshold-coloring of the graph is an assignment of integers to the vertices so that endpoints of near edges differ by t or less, while endpoints of far edges differ by more than t. We study threshold-coloring of tilings of the plane by regular polygons, known as Archimedean lattices, and their duals, the Laves lattices. We prove that some are threshold-colorable with constant number of colors for any edge labeling, some require an unbounded number of colors for specific labelings, and some are not threshold-colorable.

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

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

U2 - 10.1007/978-3-319-07890-8_3

DO - 10.1007/978-3-319-07890-8_3

M3 - Conference contribution

AN - SCOPUS:84903746702

SN - 9783319078892

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

SP - 28

EP - 39

BT - Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings

PB - Springer-Verlag

Y2 - 1 July 2014 through 3 July 2014

ER -

Happy edges: Threshold-coloring of regular lattices

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this