A \((2 + \epsilon ) k\)-vertex kernel for the dual coloring problem

DOI10.1016/j.tcs.2021.03.035zbMath1497.68391OpenAlexW3143198978MaRDI QIDQ831124

Yongjie Yang, Yang Ding, Wenjun Li, Guozhen Rong

Publication date: 10 May 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.03.035

zbMATH Keywords

kernelGallai-Edmonds decompositiondual coloringfactor-critical crown

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Matching theory
• Paths, Trees, and Flowers
• Parameterized Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: A \((2 + \epsilon ) k\)-vertex kernel for the dual coloring problem