The packing chromatic number of the square lattice is at least 12

preprint2010arXivOpen access

Abstract

The packing chromatic number χρ(G)χ_ρ(G) of a graph GG is the smallest integer kk such that the vertex set V(G)V(G) can be partitioned into disjoint classes X1,...,XkX_1, ..., X_k, where vertices in XiX_i have pairwise distance greater than ii. For the 2-dimensional square lattice Z2\mathbb{Z}^2 it is proved that χρ(Z2)≥12χ_ρ(\mathbb{Z}^2) \geq 12, which improves the previously known lower bound 10.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.