Modeling the packing coloring problem of graphs

DOI10.1016/j.apm.2014.11.060zbMath1443.05077OpenAlexW1967139416MaRDI QIDQ2009921

Zehui Shao, Aleksander Vesel

Publication date: 3 December 2019

Published in: Applied Mathematical Modelling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apm.2014.11.060

zbMATH Keywords

integer linear programmingCartesian productfrequency assignmentpacking chromatic number

Mathematics Subject Classification ID

Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12)

Related Items

Packing coloring of Sierpiński-type graphs ⋮ Packing chromatic number of base-3 Sierpiński graphs ⋮ An infinite family of subcubic graphs with unbounded packing chromatic number ⋮ 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 ⋮ On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs ⋮ General position sets in two families of Cartesian product graphs ⋮ A survey on packing colorings ⋮ \(S\)-packing chromatic vertex-critical graphs ⋮ Packing colorings of subcubic outerplanar graphs ⋮ \((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 ⋮ The packing chromatic number of the infinite square lattice is between 13 and 15 ⋮ \(S\)-packing colorings of distance graphs \(G ( \mathbb{Z} , \{ 2 , t \} )\) ⋮ Graphs that are critical for the packing chromatic number

Uses Software

• CALMA

Cites Work

• Unnamed Item
• Unnamed Item
• Packing chromatic number of distance graphs
• Complexity of the packing coloring problem for trees
• The packing chromatic number of infinite product graphs
• A lower bound for the packing chromatic number of the Cartesian product of cycles
• A note on packing chromatic number of the square lattice
• The packing coloring of distance graphs \(D(k,t)\)
• On packing colorings of distance graphs
• On the packing chromatic number of square and hexagonal lattice
• Exact Algorithms for L(2,1)-Labeling of Graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• Models and solution techniques for frequency assignment problems