Parameterized (Approximate) Defective Coloring
From MaRDI portal
Publication:5107096
DOI10.1137/18M1223666zbMath1433.68178OpenAlexW2963087827MaRDI QIDQ5107096
Rémy Belmonte, Michael Lampis, Valia Mitsou
Publication date: 22 April 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1223666
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (3)
Extended MSO model checking via small vertex integrity ⋮ Graph partitions under average degree constraint ⋮ On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- On 1-improper 2-coloring of sparse graphs
- Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
- On minimal triangle-free graphs with prescribed \(k\)-defective chromatic number
- On the complexity of some colorful problems parameterized by treewidth
- Bounds and fixed-parameter algorithms for weighted improper coloring
- Zero knowledge and the chromatic number
- Extremal results on defective colorings of graphs
- Which problems have strongly exponential complexity?
- Structurally parameterized \(d\)-Scattered Set
- Defective coloring on classes of perfect graphs
- Algorithmic meta-theorems for restrictions of treewidth
- Weighted improper colouring
- Linear time solvable optimization problems on graphs of bounded clique-width
- Directed weighted improper coloring for cellular channel allocation
- Vertex coloring edge-weighted digraphs
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Parametrized complexity theory.
- Tree-depth, subgraph coloring and homomorphism bounds
- Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions
- Parameterized Algorithms for Modular-Width
- Vertex-Coloring with Defects
- Improper coloring of unit disk graphs
- IMPROPER COLORING OF WEIGHTED GRID AND HEXAGONAL GRAPHS
- Defective coloring revisited
- Parameterized Power Vertex Cover
- Fractional, Circular, and Defective Coloring of Series-Parallel Graphs
- The t-Improper Chromatic Number of Random Graphs
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- A note on defective colorings of graphs in surfaces
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Parameterized Approximation Schemes Using Graph Widths
- Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
- Improper coloring of graphs on surfaces
- Improper choosability of graphs and maximum average degree
- Parameterized Algorithms
This page was built for publication: Parameterized (Approximate) Defective Coloring
