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

DOI10.1016/J.TCS.2021.03.035MaRDI QIDQ831124zbMATH OpenOpenAlexFDO

Authors Wen-Jun Li, Yang Ding, Yongjie Yang, 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)

Recommendations

• scientific article; zbMATH DE number 1444491
• Two complexity results for the vertex coloring problem
• Dual parameterization of weighted coloring
• Dual parameterization of weighted coloring
• An approximate algorithm for the \( (k,d)\)-coloring problem
• A kernel of order \(2k - c\) for Vertex Cover
• Kernels in edge-colored digraphs
• On digraph coloring problems and treewidth duality
• scientific article; zbMATH DE number 1433954
• On 2-dominating kernels in graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Graph-Theoretic Concepts in Computer Science
• Matching theory
• Parameterized algorithms
• Paths, Trees, and Flowers

Cited in

(3)

• Optimal data reduction for graph coloring using low-degree polynomials
• Optimal data reduction for graph coloring using low-degree polynomials
• Graph-Theoretic Concepts in Computer Science

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

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