Approximation and hardness results for the maximum edge \(q\)-coloring problem

DOI10.1016/j.jda.2016.09.003zbMath1355.68103OpenAlexW2525416008WikidataQ58203651 ScholiaQ58203651MaRDI QIDQ350721

Anna Adamaszek, Alexandru Popa

Publication date: 9 December 2016

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2016.09.003

zbMATH Keywords

graph coloringapproximation algorithmshardness of approximation

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

On \(\mathrm{M}_f\)-edge colorings of graphs ⋮ Improved approximation for maximum edge colouring problem ⋮ New bounds on the anti-Ramsey numbers of star graphs via maximum edge \(q\)-coloring ⋮ Complexity of Computing the Anti-Ramsey Numbers for Paths.

Cites Work

• Unnamed Item
• Rainbow generalizations of Ramsey theory: A survey
• On the hardness of approximating minimum vertex cover
• Approximation algorithm for maximum edge coloring
• Edge-colorings with no large polychromatic stars
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Minimal colorings for properly colored subgraphs
• On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem
• The Min-max Edge q-Coloring Problem
• Approximation and Hardness Results for the Maximum Edge q-coloring Problem
• On the power of unique 2-prover 1-round games
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Approximation Algorithms for Maximum Edge Coloring Problem
• On totally multicolored stars

This page was built for publication: Approximation and hardness results for the maximum edge \(q\)-coloring problem