Přejít k obsahu


A note on packing chromatic number of the square lattics

Citace: [] SOUKAL, R., HOLUB, P. A note on packing chromatic number of the square lattics. Electronic Journal of Combinatorics, 2010, roč. 17, č. 1, s. 1-8. ISSN: 1077-8926
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: A note on packing chromatic number of the square lattics
Rok vydání: 2010
Autoři: Ing. Roman Soukal , RNDr. Přemysl Holub Ph.D.
Abstrakt CZ: Pojem pakovací barvení je úzce spjat s problémem přiřazování frekvencí. Pakovací chromatické číslo grafu je nejmenší přirozené číslo k takové, že množinu vrcholů grafu G lze rozdělit do disjunktních podmnožin X_1, ... X_k tak, že vrcholy v množině X_i mají navzájem vzdálenost větší než i. V tomto článku jsme vylepšili horní odhad pro pakovací chromatické číslo čtvercové mřížky.
Abstrakt EN: The concept of a packing colouring is related to a frequency assignment problem. The packing chromatix number X_p(G) of a graph G is the smallest integer k such that the vertex set V (G) can be partitioned into disjoint classes X_1,..., X_k, where vertices in X_i have pairwise distance greater than i. In this note we improve the upper bound on the packing chromatic number of the square lattice.
Klíčová slova

Zpět

Patička