On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

DOI10.1016/j.dam.2007.06.008zbMath1126.05045MaRDI QIDQ5920353

Boštjan Brešar, Sandi Klavžar, Douglas F. Rall

Publication date: 29 October 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.06.008

zbMATH Keywords

tree; computational complexity; subdivision graph; Cartesian product of graphs; hexagonal lattice; Packing chromatic number

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

Related Items

Complexity of the Packing Coloring Problem for Trees, \(S\)-packing colorings of cubic graphs, Facial packing edge-coloring of plane graphs, Packing chromatic number of distance graphs, Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph, Packing chromatic number under local changes in a graph, A survey and classification of Sierpiński-type graphs, The packing chromatic number of the infinite square lattice is between 13 and 15, Complexity of the packing coloring problem for trees, On the packing chromatic number of some lattices, The packing chromatic number of infinite product graphs, Packing chromatic number of cubic graphs, A lower bound for the packing chromatic number of the Cartesian product of cycles, The packing chromatic number of hypercubes, Packing coloring of some undirected and oriented coronae graphs, Dichotomies properties on computational complexity of \(S\)-packing coloring problems, Packing chromatic number of certain fan and wheel related graphs, The packing coloring of distance graphs \(D(k,t)\), On packing colorings of distance graphs, The packing coloring problem for lobsters and partner limited graphs, Packing chromatic number of base-3 Sierpiński graphs, A note on \(S\)-packing colorings of lattices, Polynomial instances of the Packing Coloring Problem

Cites Work

• On the independence graph of a graph
• Distributive online channel assignment for hexagonal cellular networks with constraints
• 2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs
• A technique for multicoloring triangle-free hexagonal graphs
• Perfect r-domination in the Kronecker product of three cycles
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item