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

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

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

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

treecomputational complexitysubdivision graphCartesian product of graphshexagonal latticePacking chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (49)

On packing coloring of helm related graphs ⋮ Packing coloring of some undirected and oriented coronae graphs ⋮ Packing coloring of Sierpiński-type graphs ⋮ A new approach on locally checkable problems ⋮ \(S\)-packing colorings of cubic graphs ⋮ Packing chromatic number of base-3 Sierpiński graphs ⋮ An infinite family of subcubic graphs with unbounded packing chromatic number ⋮ Facial packing edge-coloring of plane graphs ⋮ Notes on complexity of packing coloring ⋮ A note on \(S\)-packing colorings of lattices ⋮ Complexity of the Packing Coloring Problem for Trees ⋮ Packing chromatic number versus chromatic and clique number ⋮ New results on radio \(k\)-labelings of distance graphs ⋮ Independence number and packing coloring of generalized Mycielski graphs ⋮ Packing chromatic numbers of finite super subdivisions of graphs ⋮ A note on the packing chromatic number of lexicographic products ⋮ On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs ⋮ Dichotomies properties on computational complexity of \(S\)-packing coloring problems ⋮ Packing chromatic number of certain fan and wheel related graphs ⋮ Packing chromatic number of cubic graphs ⋮ Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs ⋮ Packing chromatic number of distance graphs ⋮ A survey on packing colorings ⋮ \(S\)-packing chromatic vertex-critical graphs ⋮ Unnamed Item ⋮ A characterization of 4-\(\chi_S\)-vertex-critical graphs for packing sequences with \(s_1 = 1\) and \(s_2 \geq 3\) ⋮ Packing colorings of subcubic outerplanar graphs ⋮ A lower bound for the packing chromatic number of the Cartesian product of cycles ⋮ The packing coloring of distance graphs \(D(k,t)\) ⋮ On packing colorings of distance graphs ⋮ On the packing chromatic number of Moore graphs ⋮ The packing coloring problem for lobsters and partner limited graphs ⋮ On the packing chromatic number of subcubic outerplanar graphs ⋮ Facial packing vertex-coloring of subdivided plane graphs ⋮ A heuristic approach for searching \((d, n)\)-packing colorings of infinite lattices ⋮ 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 ⋮ Unnamed Item ⋮ Modeling the packing coloring problem of graphs ⋮ Complexity of the packing coloring problem for trees ⋮ On the packing chromatic number of some lattices ⋮ \(S\)-packing colorings of distance graphs \(G ( \mathbb{Z} , \{ 2 , t \} )\) ⋮ Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs ⋮ Packing colouring of some classes of cubic graphs ⋮ The packing chromatic number of infinite product graphs ⋮ Polynomial instances of the Packing Coloring Problem ⋮ The packing chromatic number of hypercubes

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

This page was built for publication: On the packing chromatic number of Cartesian products, hexagonal lattice, and trees