VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Packing coloring of hypercubes with extended Hamming codes
    Gregor, Petr ...
    A packing ▫$k$▫-coloring of a graph ▫$G$▫ is a mapping assigning a positive integer (a color) from the set ▫$\{1,\ldots,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 {\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 the packing chromatic number of Cartesian products raised by Bre\v{s}ar, Klav\v{z}ar, and Rall ({\em Problem 5, Bre\v{s}ar et al., On the packing chromatic number of Cartesian products, hexagonal lattice, and trees. Discrete Appl. Math. 155 (2007), 2303--2311.}).
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 359, 2024, str. 269-277)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2024
    Jezik - angleški
    COBISS.SI-ID - 208227331
    DOI

Vnos na polico