Parameterized Pre-Coloring Extension and List Coloring Problems

DOI10.1137/20M1323369zbMath1462.68083arXiv1907.12061OpenAlexW3014040691MaRDI QIDQ5857010

Gregory Gutin, Sebastian Ordyniak, Diptapriyo Majumdar, Magnus Wahlström

Publication date: 30 March 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringparameterized complexitylist coloringkernelization

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Parameterizing role coloring on forests ⋮ On structural parameterizations of star coloring ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ Structural parameterizations of budgeted graph coloring ⋮ Parameterized complexity of list coloring and max coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constrained multilinear detection and generalized graph motifs
• Fundamentals of parameterized complexity
• Kernel bounds for path and cycle problems
• Solving MAX-\(r\)-SAT above a tight lower bound
• Improved upper bounds for vertex cover
• Some (in)tractable parameterizations of coloring and list-coloring
• Saving colors and max coloring: some fixed-parameter tractability results
• Parameterized complexity of vertex colouring
• Vertex colouring and forbidden subgraphs -- a survey
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Narrow sieves for parameterized paths and packings
• Sparsification upper and lower bounds for graph problems and not-all-equal SAT
• Open Problems on Graph Coloring for Special Graph Classes
• Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Set Partitioning via Inclusion-Exclusion
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Graph colorings with local constraints -- a survey
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Kernelization
• Kernelization Lower Bounds Through Colors and IDs
• On Problems as Hard as CNF-SAT
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science
• Fixed-parameter tractability of \((n-k)\) list coloring

This page was built for publication: Parameterized Pre-Coloring Extension and List Coloring Problems