On the structural parameterized complexity of defective coloring

DOI10.1016/J.JCSS.2025.103736MaRDI QIDQ6859744zbMATH OpenFDO

Authors Sriram Bhyravarapu, Pankaj Kumar, Saket Saurabh

Publication date 11 February 2026

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103736

zbMATH Keywords

bounded-degree graphsdefective coloringneighborhood diversityparameterized complexitysplit graphstwin-cover

Mathematics Subject Classification ID

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

Cites work

• A single-exponential time 2-approximation algorithm for treewidth
• Algorithmic meta-theorems for restrictions of treewidth
• An application of simultaneous diophantine approximation in combinatorial optimization
• Bounds and fixed-parameter algorithms for weighted improper coloring
• Defective Coloring on Classes of Perfect Graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Defective colouring of graphs excluding a subgraph or minor
• Directed weighted improper coloring for cellular channel allocation
• Extremal results on defective colorings of graphs
• scientific article; zbMATH DE number 4008419 (Why is no real title available?)
• Improper coloring of weighted grid and hexagonal graphs
• Integer Programming with a Fixed Number of Variables
• Minimum eccentricity shortest path problem with respect to structural parameters
• Minkowski's Convex Body Theorem and Integer Programming
• On minimal triangle-free graphs with prescribed \(k\)-defective chromatic number
• Parameterized (approximate) defective coloring
• Parameterized algorithms
• Structural parameterizations for two bounded degree problems revisited
• Subcolorings and the subchromatic number of a graph
• The \(t\)-improper chromatic number of random graphs
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Vertex coloring edge-weighted digraphs
• Weighted improper colouring

This page was built for publication: On the structural parameterized complexity of defective coloring

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