A survey on packing colorings

DOI10.7151/dmgt.2320zbMath1446.05031OpenAlexW3017968798MaRDI QIDQ2194523

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

Publication date: 26 August 2020

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.2320

zbMATH Keywords

computational complexitysubcubic graphpacking chromatic numberpacking coloring\(S\)-packing chromatic number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On the packing coloring of base-3 Sierpiński graphs and \(H\)-graphs, The exponential growth of the packing chromatic number of iterated Mycielskians, Graph classes generated by Mycielskians, A characterization of 4-\(\chi_S\)-vertex-critical graphs for packing sequences with \(s_1 = 1\) and \(s_2 \geq 3\), On \(S\)-packing colourings of distance graphs \(D (1, t)\) and \(D (1, 2, t)\), Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(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
• Acyclic and \(k\)-distance coloring of the grid
• The packing chromatic number of infinite product graphs
• On the maximum average degree and the oriented chromatic number of a graph
• Packing coloring of Sierpiński-type graphs
• An infinite family of subcubic graphs with unbounded packing chromatic number
• Notes on complexity of packing coloring
• Packing chromatic number versus chromatic and clique number
• Packing chromatic number of cubic graphs
• \((d, n)\)-packing colorings of infinite lattices
• 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
• On \(S\)-packing edge-colorings of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• A lower bound for the packing chromatic number of the Cartesian product of cycles
• Modeling the packing coloring problem of graphs
• Graphs that are critical for the packing chromatic number
• Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs
• The packing chromatic number of hypercubes
• Packing coloring of some undirected and oriented coronae graphs
• A note on packing chromatic number of the square lattice
• 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
• A survey on the distance-colouring of graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Packing chromatic number of base-3 Sierpiński graphs
• A note on \(S\)-packing colorings of lattices
• The S-packing chromatic number of a graph
• The Packing Coloring Problem for (q,q-4) Graphs
• On the packing chromatic number of square and hexagonal lattice
• Subdivision into i-packings and S-packing chromatic number of some lattices
• List-coloring the square of a subcubic graph
• Graphs S(n, k) and a Variant of the Tower of Hanoi Problem
• Packing Coloring of Undirected and Oriented Generalized Theta Graphs
• Packing colouring of some classes of cubic graphs
• On packing coloring of helm related graphs
• Packing coloring of generalized Sierpinski graphs
• Packing chromatic vertex-critical graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees