Approximating maximum edge 2-coloring in simple graphs

DOI10.1016/J.DAM.2010.08.010zbMATH Open1216.05029OpenAlexW1979880971MaRDI QIDQ608271FDOQ608271

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

Recommendations

• Approximating maximum edge 2-coloring in simple graphs
• An improved approximation algorithm for maximum edge 2-coloring in simple graphs
• An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs
• Approximating maximum edge 2-coloring in simple graphs via local improvement
• Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement

zbMATH Keywords

approximation algorithmsgraph algorithmsNP-hardnessedge coloring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement
• \(M_2\)-edge coloring and maximum matching of graphs
• Online edge coloring of paths and trees with a fixed number of colors
• An approximation algorithm for covering vertices by \(4^+\)-paths
• Online Dual Edge Coloring of Paths and Trees
• Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
• Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q608271)