Polychromatic Colorings on the Hypercube

Thumbnail Image
Date
2018-01-01
Authors
Goldwasser, John
Martin, Ryan
Offner, David
Talbot, John
Young, Michael
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

Given a subgraph G of the hypercube Qn, a coloring of the edges of Qn 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.

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
article
Comments

This is a preprint made available through arxiv: https://arxiv.org/abs/1603.05865.

Published as Goldwasser, John, Bernard Lidický, Ryan R. Martin, David Offner, John Talbot, and Michael Young. "Polychromatic colorings on the hypercube." Journal of Combinatorics 9, no. 4 (2018): 631-657. DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n4.a4.

Rights Statement
Copyright
Mon Jan 01 00:00:00 UTC 2018
Funding
DOI
Supplemental Resources
Source
Collections