Grundy Distinguishes Treewidth from Pathwidth

Yota Otachi, Eun Jung Kim, Rémy Belmonte, Valia Mitsou, Michael Lampis

Publication date: 18 August 2022

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

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

zbMATH Keywords

treewidth pathwidth clique-width Grundy coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
The parameterised complexity of list problems on graphs of bounded treewidth
Satisfiability of acyclic and almost acyclic CNF formulas
Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
Parameterized maximum path coloring
Treewidth governs the complexity of target set selection
First-fit coloring on interval graphs has performance ratio at least 5
More bounds for the Grundy number of graphs
First-fit coloring of bounded tolerance graphs
Parameterized complexity of coloring problems: treewidth versus vertex cover
On the complexity of some colorful problems parameterized by treewidth
Primal-dual approximation algorithms for integral flow and multicut in trees
On bounded-degree vertex deletion parameterized by treewidth
On the parameterized complexity of spanning trees with small vertex covers
The parameterised complexity of computing the maximum modularity of a graph
Constraint satisfaction with bounded treewidth revisited
Results on the Grundy chromatic number of graphs
A note on first-fit coloring of interval graphs
The Steiner forest problem revisited
On the parameterized complexity of multiple-interval graph problems
An application of simultaneous diophantine approximation in combinatorial optimization
Some perfect coloring properties of graphs
A partial k-arboretum of graphs with bounded treewidth
On the equality of the partial Grundy and upper ochromatic numbers of graphs
Structurally parameterized \(d\)-Scattered Set
Notes on complexity of packing coloring
Time-approximation trade-offs for inapproximable problems
Matchings with lower quotas: algorithms and complexity
Counting linear extensions: parameterizations by treewidth
The complexity landscape of decompositional parameters for ILP
Complexity of Grundy coloring and its variants
Algorithmic meta-theorems for restrictions of treewidth
On the Grundy number of graphs with few \(P_4\)'s
Parameterized complexity of length-bounded cuts and multicuts
On the Grundy and \(b\)-chromatic numbers of a graph
Linear time solvable optimization problems on graphs of bounded clique-width
Metric dimension parameterized by treewidth
Parameterized complexity of \((A,\ell)\)-path packing
Length-bounded cuts: proper interval graphs and structural parameters
Parameterized complexity of safe set
Complexity and approximability of parameterized MAX-CSPs
Structural parameters, tight bounds, and approximation for \((k, r)\)-center
On the complexity of restoring corrupted colorings
Tractable cases of the extended global cardinality constraint
Inequalities for the Grundy chromatic number of graphs
Tree-depth, subgraph coloring and homomorphism bounds
The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
Parameterized Algorithms for Modular-Width
No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
Integer Programming with a Fixed Number of Variables
On Tractable Cases of Target Set Selection
Parameterized Power Vertex Cover
On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
Capacitated Domination and Covering: A Parameterized Perspective
Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
What Makes Equitable Connected Partition Easy
Minkowski's Convex Body Theorem and Integer Programming
On-line and first fit colorings of graphs
Algorithms for Vertex Partitioning Problems on Partial k-Trees
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
Clique-width III
An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
New Results on Directed Edge Dominating Set
Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
On Routing Disjoint Paths in Bounded Treewidth Graphs
Model Checking Lower Bounds for Simple Graphs
Parameterized Algorithms

This page was built for publication: Grundy Distinguishes Treewidth from Pathwidth