Complexity of the packing coloring problem for trees

DOI10.1016/j.dam.2008.09.001zbMath1219.05185OpenAlexW2151433687MaRDI QIDQ972338

Jiří Fiala, Petr A. Golovach

Publication date: 25 May 2010

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

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

zbMATH Keywords

treecomputational complexitygraph algorithmchordal graphpacking coloring

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (42)

On packing coloring of helm related 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 ⋮ Packing chromatic number versus chromatic and clique number ⋮ 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 ⋮ 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 ⋮ The exponential growth of the packing chromatic number of iterated Mycielskians ⋮ Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs ⋮ Packing chromatic number of distance graphs ⋮ A survey on packing colorings ⋮ On packing \(S\)-colorings of subcubic graphs ⋮ 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 ⋮ 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 ⋮ On \(S\)-packing edge-colorings of cubic graphs ⋮ Packing chromatic number of subdivisions of cubic 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 ⋮ Unnamed Item ⋮ Modeling the packing coloring problem of graphs ⋮ Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs ⋮ The packing chromatic number of infinite product graphs ⋮ On \(S\)-packing edge-colorings of graphs with small edge weight ⋮ Polynomial instances of the Packing Coloring Problem ⋮ The packing chromatic number of hypercubes ⋮ Graphs that are critical for the packing chromatic number

Cites Work

• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of the packing coloring problem for trees