Approximation and hardness results for the maximum edge \(q\)-coloring problem
From MaRDI portal
Publication:350721
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
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
