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

DOI10.1016/J.TCS.2021.03.035zbMATH Open1497.68391OpenAlexW3143198978MaRDI QIDQ831124FDOQ831124

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

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

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

• Title not available (Why is that?)
• 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

Cited In (3)

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

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)