The complexity of tree multicolorings

DOI10.1007/3-540-45687-2_44MaRDI QIDQ4708601zbMATH OpenFDO

Authors Dániel Marx

Publication date 18 June 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2420/24200532.htm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Minimum sum multicoloring on the edges of trees
• Multicoloring trees.
• Approximation and Online Algorithms
• Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
• STACS 2004

Cited in

(14)

• List edge multicoloring in graphs with few cycles
• The color-degree matrix and the number of multicolored trees in star decompositions
• Multicoloring trees.
• A polynomial algorithm for some preemptive multiprocessor task scheduling problems
• Minimum sum multicoloring on the edges of trees
• Algorithms for the multicolorings of partial k-trees
• On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
• Tight lower bounds for the complexity of multicoloring
• scientific article; zbMATH DE number 6730060 (Why is no real title available?)
• Approximation and Online Algorithms
• On the complexity of some colorful problems parameterized by treewidth
• Minimum sum set coloring of trees and line graphs of trees
• On sum coloring and sum multi-coloring for restricted families of graphs
• A note on mixed tree coloring

This page was built for publication: The complexity of tree multicolorings

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