Journal of Combinatorics

Volume 9 (2018)

Number 4

Polychromatic colorings on the hypercube

Pages: 631 – 657

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n4.a4

Authors

John Goldwasser (Department of Mathematics, West Virginia University, Morgantown, W.V., U.S.A.)

Bernard Lidický (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Ryan R. Martin (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

David Offner (Department of Mathematics, Westminster College, New Wilmington, Pennsylvania, U.S.A.)

John Talbot (Department of Mathematics, , University College London, United Kingdom)

Michael Young (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Abstract

Given a subgraph $G$ of the hypercube $Q_n$, a coloring of the edges of $Q_n$ such that every embedding of $G$ contains an edge of every color is called a $G$-polychromatic coloring. The maximum number of colors with which it is possible to $G$-polychromatically color the edges of any hypercube is called the polychromatic number of $G$. To determine polychromatic numbers, it is only necessary to consider a specific type of coloring, which we call simple. The main tool for finding upper bounds on polychromatic numbers is to translate the question of polychromatically coloring the hypercube so every embedding of a graph $G$ contains every color into a question of coloring the $2$-dimensional grid so that every so-called shape sequence corresponding to $G$ contains every color. After surveying the tools for finding polychromatic numbers, we apply these techniques to find polychromatic numbers of a class of graphs called punctured hypercubes. We also consider the problem of finding polychromatic numbers in the setting where larger subcubes of the hypercube are colored. We exhibit two new constructions which show that this problem is not a straightforward generalization of the edge coloring problem.

Keywords

polychromatic coloring, hypercube, coloring, Turán

2010 Mathematics Subject Classification

05C15, 05C35

Full Text (PDF format)

Bernard Lidicky was supported in part by NSF grants DMS-1266016 and DMS-1600390.

Ryan R. Martin was supported in part by National Security Agency grant H98230-13-1-0226 and by Simons Foundation grant #353292

Received 17 March 2016

Published 7 December 2018