Complexity of the Packing Coloring Problem for Trees

DOI10.1007/978-3-540-92248-3_13zbMath1202.05025OpenAlexW2114664772MaRDI QIDQ5302050

Jiří Fiala, Petr A. Golovach

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_13

zbMATH Keywords

computational complexitygraph algorithmchordal graphpacking coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Packing coloring of some undirected and oriented coronae graphs

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
• Tree Powers
• Algorithms for Square Roots of Graphs
• On the packing chromatic number of Cartesian products, hexagonal lattice, and trees
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of the Packing Coloring Problem for Trees