Grundy distinguishes treewidth from pathwidth
From MaRDI portal
Publication:5874480
DOI10.4230/LIPICS.ESA.2020.14MaRDI QIDQ5874480FDOQ5874480
Authors: Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi 
Publication date: 7 February 2023
Recommendations
Cites Work
- Some perfect coloring properties of graphs
- Algorithmic meta-theorems for restrictions of treewidth
- Linear time solvable optimization problems on graphs of bounded clique-width
- Tractable cases of the extended global cardinality constraint
- Tree-depth, subgraph coloring and homomorphism bounds
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Treewidth governs the complexity of target set selection
- Parameterized algorithms
- Satisfiability of acyclic and almost acyclic CNF formulas
- Constraint satisfaction with bounded treewidth revisited
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Results on the Grundy chromatic number of graphs
- On bounded-degree vertex deletion parameterized by treewidth
- On the parameterized complexity of multiple-interval graph problems
- Parameterized Algorithms for Modular-Width
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- On-line and first fit colorings of graphs
- Algorithmic lower bounds for problems parameterized by clique-width
- Inequalities for the Grundy chromatic number of graphs
- Title not available (Why is that?)
- A lower bound for approximating the Grundy number
- Primal-dual approximation algorithms for integral flow and multicut in trees
- The mixed Chinese postman problem parameterized by pathwidth and treedepth
- The parameterised complexity of list problems on graphs of bounded treewidth
- On the complexity of some colorful problems parameterized by treewidth
- Capacitated Domination and Covering: A Parameterized Perspective
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Parameterized maximum path coloring
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Model checking lower bounds for simple graphs
- On the equality of the partial Grundy and upper ochromatic numbers of graphs
- Complexity and approximability of parameterized MAX-CSPs
- What makes equitable connected partition easy
- First-fit coloring on interval graphs has performance ratio at least 5
- A note on first-fit coloring of interval graphs
- More bounds for the Grundy number of graphs
- On tractable cases of target set selection
- First-fit coloring of bounded tolerance graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Grundy number of graphs with few \(P_4\)'s
- On the parameterized complexity of spanning trees with small vertex covers
- Counting linear extensions: parameterizations by treewidth
- The parameterised complexity of computing the maximum modularity of a graph
- Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus
- On structural parameterizations of the bounded-degree vertex deletion problem
- Known algorithms on graphs of bounded treewidth are probably optimal
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- The Steiner forest problem revisited
- Parameterized complexity of length-bounded cuts and multicuts
- Structurally parameterized \(d\)-scattered set
- Time-approximation trade-offs for inapproximable problems
- Parameterized complexity of fair vertex evaluation problems
- Matchings with lower quotas: algorithms and complexity
- The complexity landscape of decompositional parameters for ILP
- New algorithms for maximum disjoint paths based on tree-likeness
- On routing disjoint paths in bounded treewidth graphs
- Parameterized (approximate) defective coloring
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- New results on directed edge dominating set
- Parameterized complexity of safe set
- Treewidth with a quantifier alternation revisited
- On the complexity of restoring corrupted colorings
Cited In (8)
- On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems
- Grundy Distinguishes Treewidth from Pathwidth
- In)approximability of Maximum Minimal FVS
- Extended MSO model checking via small vertex integrity
- \(b\)-coloring parameterized by clique-width
- (In)approximability of maximum minimal FVS
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Exploring the gap between treedepth and vertex cover through vertex integrity
This page was built for publication: Grundy distinguishes treewidth from pathwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874480)
