Dichotomies properties on computational complexity of \(S\)-packing coloring problems

DOI10.1016/j.disc.2015.01.028zbMath1371.05080arXiv1312.5280OpenAlexW2032843850MaRDI QIDQ2407038

Nicolas Gastineau

Publication date: 28 September 2017

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

Full work available at URL: https://arxiv.org/abs/1312.5280

zbMATH Keywords

graphNP-complete problempacking chromatic number\(d\)-distance coloring\(S\)-packing chromatic number

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Packing coloring of some undirected and oriented coronae graphs, Packing coloring of Sierpiński-type graphs, \(S\)-packing colorings of cubic graphs, Packing chromatic number of base-3 Sierpiński graphs, Packing chromatic number versus chromatic and clique number, Spectrum graph coloring and applications to Wi-Fi channel assignment, Packing chromatic number of cubic graphs, Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction, Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs, A survey on packing colorings, On packing \(S\)-colorings of subcubic graphs, \(S\)-packing chromatic vertex-critical graphs, A characterization of 4-\(\chi_S\)-vertex-critical graphs for packing sequences with \(s_1 = 1\) and \(s_2 \geq 3\), Packing chromatic number of subdivisions of cubic graphs, Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph, \(S\)-packing colorings of distance graphs \(G ( \mathbb{Z} , \{ 2 , t \} )\), Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs

Cites Work

• Graph minors. III. Planar tree-width
• Complexity of the packing coloring problem for trees
• On the packing chromatic number of some lattices
• Quickly excluding a forest
• A note on \(S\)-packing colorings of lattices
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Über eine Eigenschaft der ebenen Komplexe
• Polynomial instances of the Packing Coloring Problem
• The S-packing chromatic number of a graph
• On Distance Coloring
• The Packing Coloring Problem for (q,q-4) Graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• Unnamed Item