Improved approximation for maximum edge colouring problem
From MaRDI portal
Publication:2161229
DOI10.1016/j.dam.2021.05.017zbMath1494.05044arXiv1910.11753WikidataQ114191490 ScholiaQ114191490MaRDI QIDQ2161229
Nitin Singh, L. Sunil Chandran, Abhiruk Lahiri
Publication date: 4 August 2022
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1910.11753
05C15: Coloring of graphs and hypergraphs
05C55: Generalized Ramsey theory
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
05D10: Ramsey theory
Related Items
Cites Work
- Unnamed Item
- Approximation and hardness results for the maximum edge \(q\)-coloring problem
- The anti-Ramsey number of perfect matching
- On restricted colourings of \(K_ n\)
- Approximation algorithm for maximum edge coloring
- A rainbow \(k\)-matching in the complete graph with \(r\) colors
- Edge-colorings of complete graphs that avoid polychromatic trees
- Edge-colorings with no large polychromatic stars
- Anti-Ramsey colorings in several rounds
- Anti-Ramsey numbers of subdivided graphs
- Rainbow numbers for matchings and complete graphs
- Minimal colorings for properly colored subgraphs
- An anti-Ramsey theorem on cycles
- On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem
- Rainbow numbers for small stars with one edge added
- Approximation and Hardness Results for the Maximum Edge q-coloring Problem
- Bipartite anti-Ramsey numbers of cycles
- On a conjecture of erdöus, simonovits, and sós concerning anti‐Ramsey theorems
- On the Erdős–Simonovits–Sós Conjecture about the Anti-Ramsey Number of a Cycle
- On totally multicolored stars
- An anti-Ramsey theorem
