On the Packing Chromatic Number on Hamming Graphs and General Graphs

2015/10/19 by Graciela Nasini, Nasini, Graciela, Daniel Severín +4
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Optimization and Search Problems #cs.DM

paper · pdf · doi:10.48550/arxiv.1510.05524

Accepted in Simpósio Brasileiro de Pesquisa Operacional XLVII (SBPO 2015) Web page: http://cdsid.org.br/sbpo2015

arxiv created 2015/10/19 · arxiv updated 2015/10/20

Abstract

The packing chromatic number χ_ρ(G) of a graph G is the smallest integer k needed to proper color the vertices of G in such a way the distance between any two vertices having color i be at least i+1. We obtain χ_ρ(H_q,m) for m=3, where H_q,m is the Hamming graph of words of length m and alphabet with q symbols, and tabulate bounds of them for m ≥ 4 up to 10000 vertices. We also give a polynomial reduction from the problem of finding χ_ρ(G) to the Maximum Stable Set problem.

Related

• Packing chromatic number under local changes in a graph
• The packing chromatic number of the square lattice is at least 12
• A note on the packing chromatic number of lexicographic products
• Graphs that are critical for the packing chromatic number
• Packing chromatic number of subdivisions of cubic graphs