Total difference chromatic numbers of regular infinite graphs

Benson-Tilsen, Noam; Brock, Samuel; Faunce, Brandon; Kumar, Monish; Stein, Noah Dokko; Zelinsky, Joshua

doi:10.2140/involve.2023.16.765

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Total difference chromatic numbers of regular infinite graphs

Noam Benson-Tilsen, Samuel Brock, Brandon Faunce, Monish Kumar, Noah Dokko Stein and Joshua Zelinsky

Vol. 16 (2023), No. 5, 765–781

DOI: 10.2140/involve.2023.16.765

Abstract

Given a graph $G$ , a $k$ -total difference labeling of the graph is a total labeling $f$ from the set of edges and vertices to the set ${1, 2, \dots, k}$ satisfying $f ({u, v}) = | f (u) - f (v) |$ for any edge ${u, v}$ . If $G$ is a graph, then $χ_{td} (G)$ is the minimum $k$ such that there is a $k$ -total difference labeling of $G$ in which no two adjacent labels are identical. We extend prior work on total difference labeling by improving the upper bound on $χ_{td} (K_{n})$ and also by proving results concerning infinite regular graphs.

Keywords

graph coloring, chromatic number

Mathematical Subject Classification

Primary: 05C15

Secondary: 05C63

Milestones

Received: 3 August 2021

Revised: 6 November 2022

Accepted: 13 November 2022

Published: 9 December 2023

Communicated by Kenneth S. Berenhaut

Authors

Noam Benson-Tilsen
Cornell University Ithaca, NY United States

Samuel Brock
Yale University New Haven, CT United States

Brandon Faunce
Rochester Institute of Technology Rochester, NY United States

Monish Kumar
Hopkins School New Haven, CT United States

Noah Dokko Stein
Yale University New Haven, CT United States

Joshua Zelinsky
Hopkins School New Haven, CT United States

Vol. 16, No. 5, 2023