Packing coloring of hypercubes with extended Hamming codes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493097" target="_blank" >RIV/00216208:11320/24:10493097 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=KZWuynYwkt" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=KZWuynYwkt</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2024.07.048" target="_blank" >10.1016/j.dam.2024.07.048</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Packing coloring of hypercubes with extended Hamming codes

Popis výsledku v původním jazyce

A packing k-coloring of a graph G is a mapping assigning a positive integer (a color) from the set {1,. .. , k} to every vertex of G such that every two distinct vertices of color c are at distance at least c + 1. The minimum value k such that G admits a packing k-coloring is called the 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 (2015) 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 the packing chromatic number of Cartesian products raised by Brešar et al. (2007).

Název v anglickém jazyce

Packing coloring of hypercubes with extended Hamming codes

Popis výsledku anglicky

A packing k-coloring of a graph G is a mapping assigning a positive integer (a color) from the set {1,. .. , k} to every vertex of G such that every two distinct vertices of color c are at distance at least c + 1. The minimum value k such that G admits a packing k-coloring is called the 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 (2015) 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 the packing chromatic number of Cartesian products raised by Brešar et al. (2007).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-15272S" target="_blank" >GA22-15272S: Principy kombinatorického generování</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

1872-6771

Svazek periodika

359

Číslo periodika v rámci svazku

prosinec

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

9

Strana od-do

269-277

Kód UT WoS článku

001299282400001

EID výsledku v databázi Scopus

2-s2.0-85201370920