On \(d\)-stable locally checkable problems parameterized by mim-width
DOI10.1016/j.dam.2023.12.015arXiv2203.15724OpenAlexW4390565234MaRDI QIDQ6202932
Carolina Lucía Gonzalez, F. Mann
Publication date: 27 February 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2203.15724
coloring\(b\)-coloringmim-widthconflict-free coloringlocally checkable problemvertex partitioning problem\([k\)-Roman domination]\(d\)-stabilityDN logic
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the signed total Roman domination and domatic numbers of graphs
- Double Roman domination
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Algorithmic aspects of homophyly of networks
- Perfect double Roman domination of trees
- The b-chromatic number of a graph
- Roman domination in graphs.
- Maximizing happiness in graphs of bounded clique-width
- Conflict-free coloring: graphs of bounded clique width and intersection graphs
- A new approach on locally checkable problems
- Dual domination problems in graphs
- Parameterized complexity of happy coloring problems
- Outer independent double Roman domination
- Independent double Roman domination in graphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- On the thinness and proper thinness of a graph
- Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees
- Signed Roman domination in graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Triple Roman domination in graphs
- Complexity and approximability of the happy set problem
- Locally boundedk-colorings of trees
- The Complexity of Coloring Circular Arcs and Chords
- More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
- Parameterized algorithms for the happy set problem
- Bounding the mim‐width of hereditary graph classes
This page was built for publication: On \(d\)-stable locally checkable problems parameterized by mim-width
