Mixed graph coloring is W[1]-hard parameterized by treewidth and paraNP-hard by neighborhood diversity, but FPT parameterized by the introduced mixed neighborhood diversity.
ACM Transaction of Algorithms14(2), 13:1–13:30 (2018)
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
years
2026 4verdicts
UNVERDICTED 4roles
background 1polarities
background 1representative citing papers
Proves fine-grained nearly ETH-tight bounds for Courcelle's theorem depending on treewidth t and the number of first-order and second-order variables in each quantifier alternation block of the MSO formula.
Provides algorithms and complexity results for the δ-Dispersion and δ-Covering problems on bounded-treewidth graphs for integer, rational, and irrational distances.
DSQ is W[1]-hard on degeneracy-2 and K_{3,3}-free graphs but FPT parameterized by solution size plus treewidth, FPT on nowhere dense classes, and admits subexponential algorithms on apex-minor-free graphs via bidimensionality.
citing papers explorer
-
The Parameterized Complexity of Coloring Mixed Graphs
Mixed graph coloring is W[1]-hard parameterized by treewidth and paraNP-hard by neighborhood diversity, but FPT parameterized by the introduced mixed neighborhood diversity.
-
Fine-Grained Bounds for Courcelle's Theorem
Proves fine-grained nearly ETH-tight bounds for Courcelle's theorem depending on treewidth t and the number of first-order and second-order variables in each quantifier alternation block of the MSO formula.
-
Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances
Provides algorithms and complexity results for the δ-Dispersion and δ-Covering problems on bounded-treewidth graphs for integer, rational, and irrational distances.
-
Dominating Set with Quotas: Balancing Coverage and Constraints
DSQ is W[1]-hard on degeneracy-2 and K_{3,3}-free graphs but FPT parameterized by solution size plus treewidth, FPT on nowhere dense classes, and admits subexponential algorithms on apex-minor-free graphs via bidimensionality.