Approximating the maximum 3- and 4-edge-colorable subgraph (extended abstract)

DOI10.1007/978-3-642-13731-0_37MaRDI QIDQ3569908zbMATH OpenOpenAlexFDO

Authors Marcin Kamiński, Łukasz Kowalik

Publication date 22 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13731-0_37

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Approximating the maximum 3-edge-colorable subgraph problem
• Beyond the Vizing's bound for at most seven colors
• scientific article; zbMATH DE number 2089961
• A better than “best possible” algorithm to edge color multigraphs

Cited in

(8)

• Improved Inapproximability Results for Maximum k-Colorable Subgraph
• Approximating the maximum 3-edge-colorable subgraph problem
• On maximum \(k\)-edge-colorable subgraphs of bipartite graphs
• Complexity of approximation of 3-edge-coloring of graphs
• Approximation of 3-Edge-Coloring of Cubic Graphs
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Beyond the Vizing's bound for at most seven colors
• Online Dual Edge Coloring of Paths and Trees

This page was built for publication: Approximating the maximum 3- and 4-edge-colorable subgraph (extended abstract)

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