Parameterized complexity of \textsc{maximum edge colorable subgraph}

DOI10.1007/978-3-030-58150-3_50OpenAlexW3082824253MaRDI QIDQ2019513

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

Publication date: 21 April 2021

Full work available at URL: https://arxiv.org/abs/2008.07953

zbMATH Keywords

edge coloringkernelizationFPT algorithmskernel lower bound

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (2)

Characterization of saturated graphs related to pairs of disjoint matchings ⋮ Pairs of disjoint matchings and related classes of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Improved upper bounds for vertex cover
• Graph edge coloring: a survey
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• Integer Programming with a Fixed Number of Variables
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Minkowski's Convex Body Theorem and Integer Programming
• The NP-Completeness of Edge-Coloring
• Color-coding
• Kernelization
• NP completeness of finding the chromatic index of regular graphs
• Parameterized Algorithms
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: Parameterized complexity of \textsc{maximum edge colorable subgraph}