Approximating maximum edge 2-coloring in simple graphs

DOI10.1016/j.dam.2010.08.010zbMath1216.05029OpenAlexW1979880971MaRDI QIDQ608271

Sayuri Konno, Zhi-Zhong Chen, Yuki Matsushita

Publication date: 25 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.08.010

zbMATH Keywords

edge coloringgraph algorithmsapproximation algorithmsNP-hardness

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (4)

Online Dual Edge Coloring of Paths and Trees ⋮ Online edge coloring of paths and trees with a fixed number of colors ⋮ Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture ⋮ Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Algorithmic aspects in information and management. Third international conference, AAIM 2007, Portland, OR, USA, June 6--8, 2007. Proceedings.
• Packing \([1, \Delta \)-factors in graphs of small degree]
• Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement
• Path factors in cubic graphs
• Complexity of Recognizing Equal Unions in Families of Sets

This page was built for publication: Approximating maximum edge 2-coloring in simple graphs