Efficient approximation algorithms for the achromatic number

DOI10.1016/j.tcs.2006.05.007zbMath1102.68140OpenAlexW2049736657MaRDI QIDQ2503345

Piotr Krysta, Krzysztof Loryś

Publication date: 14 September 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.05.007

zbMATH Keywords

graph coloringachromatic numberapproximation algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Achromatic number of fragmentable graphs

Cites Work

• Concerning the achromatic number of graphs
• Advances in graph theory
• The achromatic number of bounded degree trees
• Achromatic number is NP-complete for cographs and interval graphs
• On Approximating the Achromatic Number
• Edge Dominating Sets in Graphs
• The Harmonious Chromatic Number of Bounded Degree Trees
• The achromatic number of a graph
• Algorithms - ESA 2003
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient approximation algorithms for the achromatic number