Packing coloring of hypercubes with extended Hamming codes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910571340759040 |
|---|---|
| author | Gregor, Petr Kranjc, Jaka Lužar, Borut Štorgel, Kenny |
| author_facet | Gregor, Petr Kranjc, Jaka Lužar, Borut Štorgel, Kenny |
| contents | A {\em packing coloring} of a graph $G$ is a mapping assigning a positive integer (a color) to every vertex of $G$ such that every two vertices of color $k$ are at distance at least $k+1$. The least number of colors needed for a packing coloring of $G$ is called the {\em packing chromatic number} of $G$. In this paper, we continue the study of the packing chromatic number of hypercubes and we improve the upper bounds reported by Torres and Valencia-Pabon ({\em P. Torres, M. Valencia-Pabon, The packing chromatic number of hypercubes, Discrete Appl. Math. 190--191 (2015), 127--140}) by presenting recursive constructions of subsets of distant vertices making use of the properties of the extended Hamming codes. We also answer in negative a question on packing coloring of Cartesian products raised by Brešar, Klavžar, and Rall ({\em Problem 5, Brešar et al., On the packing chromatic number of Cartesian products, hexagonal lattice, and trees. Discrete Appl. Math. 155 (2007), 2303--2311.}). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_14576 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Packing coloring of hypercubes with extended Hamming codes Gregor, Petr Kranjc, Jaka Lužar, Borut Štorgel, Kenny Combinatorics Discrete Mathematics 05C15 (Primary), 05C12, 05C69, 05C70, 94B05 (Secondary) A {\em packing coloring} of a graph $G$ is a mapping assigning a positive integer (a color) to every vertex of $G$ such that every two vertices of color $k$ are at distance at least $k+1$. The least number of colors needed for a packing coloring of $G$ is called the {\em packing chromatic number} of $G$. In this paper, we continue the study of the packing chromatic number of hypercubes and we improve the upper bounds reported by Torres and Valencia-Pabon ({\em P. Torres, M. Valencia-Pabon, The packing chromatic number of hypercubes, Discrete Appl. Math. 190--191 (2015), 127--140}) by presenting recursive constructions of subsets of distant vertices making use of the properties of the extended Hamming codes. We also answer in negative a question on packing coloring of Cartesian products raised by Brešar, Klavžar, and Rall ({\em Problem 5, Brešar et al., On the packing chromatic number of Cartesian products, hexagonal lattice, and trees. Discrete Appl. Math. 155 (2007), 2303--2311.}). |
| title | Packing coloring of hypercubes with extended Hamming codes |
| topic | Combinatorics Discrete Mathematics 05C15 (Primary), 05C12, 05C69, 05C70, 94B05 (Secondary) |
| url | https://arxiv.org/abs/2312.14576 |