Complexity of the packing coloring problem for trees

DOI10.1016/J.DAM.2008.09.001zbMATH Open1219.05185OpenAlexW2151433687MaRDI QIDQ972338FDOQ972338

Authors: 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

Recommendations

• Complexity of the Packing Coloring Problem for Trees
• Dichotomies properties on computational complexity of \(S\)-packing coloring problems
• Packing problems in edge-colored graphs
• Notes on complexity of packing coloring
• The packing coloring problem for \((q,q-4)\) graphs
• Broadcast chromatic numbers of graphs
• Polynomial instances of the packing coloring problem
• Graph packings
• A survey on packing colorings
• The packing coloring problem for lobsters and partner limited graphs

zbMATH Keywords

treecomputational complexitygraph algorithmchordal graphpacking coloring

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Easy problems for tree-decomposable graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Broadcast chromatic numbers of 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs

Cited In (49)

• Packing chromatic number of base-3 Sierpiński graphs
• Facial packing vertex-coloring of subdivided plane graphs
• A survey and classification of Sierpiński-type graphs
• A lower bound for the packing chromatic number of the Cartesian product of cycles
• Modeling the packing coloring problem of graphs
• Notes on complexity of packing coloring
• A new approach on locally checkable problems
• The packing coloring problem for \((q,q-4)\) graphs
• A study on packing coloring of fan and jump graph families
• The packing coloring problem for lobsters and partner limited graphs
• \(S\)-packing colorings of cubic graphs
• An infinite family of subcubic graphs with unbounded packing chromatic number
• On uniquely packable trees
• Packing chromatic number versus chromatic and clique number
• A survey on packing colorings
• On packing coloring of helm related graphs
• Facial packing edge-coloring of plane graphs
• The exponential growth of the packing chromatic number of iterated Mycielskians
• Packing chromatic number of distance graphs
• On packing \(S\)-colorings of subcubic graphs
• The packing chromatic number of infinite product graphs
• Graphs that are critical for the packing chromatic number
• Independence number and packing coloring of generalized Mycielski graphs
• A note on the packing chromatic number of lexicographic products
• Packing \(( 1 , 1 , 2 , 4 )\)-coloring of subcubic outerplanar graphs
• Polynomial instances of the packing coloring problem
• Packing coloring of Sierpiński-type graphs
• On packing colorings of distance graphs
• Packing chromatic number of cubic graphs
• The complexity of the node capacitated in-tree packing problem
• On \(S\)-packing edge-colorings of cubic graphs
• Packing chromatic number of subdivisions of cubic graphs
• Broadcast chromatic numbers of graphs
• Packing \(( 1 , 1 , 2 , 2 )\)-coloring of some subcubic graphs
• Packing colorings of subcubic outerplanar graphs
• Independence, matching and packing coloring of the iterated Mycielskian of graphs
• On the packing chromatic number of subcubic outerplanar graphs
• On \(S\)-packing edge-colorings of graphs with small edge weight
• Dichotomies properties on computational complexity of \(S\)-packing coloring problems
• A note on \(S\)-packing colorings of lattices
• Packing chromatic number, \((1, 1, 2, 2)\)-colorings, and characterizing the Petersen graph
• Packing chromatic number under local changes in a graph
• \(S\)-packing chromatic vertex-critical graphs
• The packing coloring of distance graphs \(D(k,t)\)
• Packing chromatic number of certain fan and wheel related graphs
• Packing chromatic numbers of finite super subdivisions of graphs
• The packing chromatic number of hypercubes
• Complexity of the Packing Coloring Problem for Trees
• The packing chromatic number of the infinite square lattice is between 13 and 15

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972338)