Approximating the maximum 2- and 3-edge-colorable subgraph problems

DOI10.1016/j.dam.2009.04.002zbMath1227.05145OpenAlexW1973759622MaRDI QIDQ967422

Adrian Kosowski

Publication date: 28 April 2010

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

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

zbMATH Keywords

approximation algorithm\(k\)-edge-colorable subgraph problemedge coloring of graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items (11)

Characterization of saturated graphs related to pairs of disjoint matchings ⋮ Parameterized and approximation algorithms for finding two disjoint matchings ⋮ Online Dual Edge Coloring of Paths and Trees ⋮ Edge coloring: a natural model for sports scheduling ⋮ Approximating maximum edge 2-coloring in simple graphs ⋮ Online edge coloring of paths and trees with a fixed number of colors ⋮ On maximum \(k\)-edge-colorable subgraphs of bipartite graphs ⋮ ON 4-EDGE COLORING OF CUBIC GRAPHS CONTAINING “SMALL” NON-PLANAR SUBGRAPHS ⋮ Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture ⋮ Approximating maximum edge 2-coloring in simple graphs via local improvement ⋮ Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Cites Work

• Unnamed Item
• Unnamed Item
• An improved approximation algorithm for maximum edge 2-coloring in simple graphs
• Approximating the maximum 3-edge-colorable subgraph problem
• A matching problem with side conditions
• A constructive proof of Vizing's theorem
• On-line edge-coloring with a fixed number of colors
• On list edge-colorings of subcubic graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Packing \([1, \Delta \)-factors in graphs of small degree]
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs

This page was built for publication: Approximating the maximum 2- and 3-edge-colorable subgraph problems