Parameterized complexity of maximum edge colorable subgraph

DOI10.1007/S00453-022-01003-0OpenAlexW3075687921WikidataQ114229325 ScholiaQ114229325MaRDI QIDQ2088595FDOQ2088595

Abhishek Sahu, Madhumita Kundu, Akanksha Agrawal, Saket Saurabh, Prafullkumar Tale

Publication date: 6 October 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01003-0

zbMATH Keywords

edge coloringkernelizationFPT algorithmskernel lower bound

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• The NP-Completeness of Edge-Coloring
• Color-coding
• Parameterized Algorithms
• Improved upper bounds for vertex cover
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• NP completeness of finding the chromatic index of regular graphs
• Improved Parameterized Upper Bounds for Vertex Cover
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• Graph edge coloring: a survey
• Kernelization
• Paths to Trees and Cacti
• Parameterized algorithms and kernels for rainbow matching
• Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT

Cited In (2)

• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Maximum \(\Delta \)-edge-colorable subgraphs of class II graphs

Recommendations

• Title not available (Why is that?) 👍 👎
• Approximating the maximum 3-edge-colorable subgraph problem 👍 👎
• Parameterized complexity of vertex colouring 👍 👎
• Approximating the maximum 2- and 3-edge-colorable subgraph problems 👍 👎
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs 👍 👎
• On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem 👍 👎
• On the Complexity of the Max-Edge-Coloring Problem with Its Variants 👍 👎
• The Maximum k-Colorable Subgraph Problem and Related Problems 👍 👎
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs 👍 👎
• Parameterized complexity of \textsc{maximum edge colorable subgraph} 👍 👎

This page was built for publication: Parameterized complexity of maximum edge colorable subgraph

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