Approximating the maximum 3-edge-colorable subgraph problem

DOI10.1016/j.disc.2008.11.017zbMath1285.05067OpenAlexW2033199347MaRDI QIDQ1043590

Romeo Rizzi

Publication date: 9 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2008.11.017

zbMATH Keywords

approximation algorithmedge-coloringPetersen graphodd girth3-edge-coloring

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (14)

Parameterized and approximation algorithms for finding two disjoint matchings ⋮ On parsimonious edge-colouring of graphs with maximum degree three ⋮ Online Dual Edge Coloring of Paths and Trees ⋮ Maximum Δ-edge-colorable subgraphs of class II graphs ⋮ Decomposition of class II graphs into two class I graphs ⋮ Online edge coloring of paths and trees with a fixed number of colors ⋮ On disjoint matchings in cubic graphs: maximum 2-edge-colorable and maximum 3-edge-colorable subgraphs ⋮ On maximum \(k\)-edge-colorable subgraphs of bipartite graphs ⋮ Measures of edge-uncolorability of cubic 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 the maximum 2- and 3-edge-colorable subgraph problems ⋮ Parsimonious edge-coloring on surfaces ⋮ Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

Cites Work

• Unnamed Item
• Unnamed Item
• A matching problem with side conditions
• A constructive proof of Vizing's theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs
• An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs

This page was built for publication: Approximating the maximum 3-edge-colorable subgraph problem