scientific article; zbMATH DE number 7765416
From MaRDI portal
Publication:6065467
DOI10.4230/lipics.isaac.2020.58arXiv2009.08353MaRDI QIDQ6065467
Astrid Pieterse, Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Paweł Rzążewski
Publication date: 14 November 2023
Full work available at URL: https://arxiv.org/abs/2009.08353
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of the list homomorphism problem for graphs
- Best-case and worst-case sparsifiability of Boolean CSPs
- \(H\)-coloring dichotomy revisited
- List homomorphisms of graphs with bounded degrees
- A new line of attack on the dichotomy conjecture
- Dichotomy for bounded degree \(H\)-colouring
- On the complexity of \(H\)-colouring planar graphs
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- The complexity of \(H\)-colouring of bounded degree graphs
- NP-completeness of a family of graph-colouring problems
- List homomorphisms and circular arc graphs
- Optimal data reduction for graph coloring using low-degree polynomials
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- On sparsification for computing treewidth
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- A New Proof of the H-Coloring Dichotomy
- The power of primitive positive definitions with polynomially many variables
- On the complexity of the general coloring problem
- Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy
- Kernelization
- Bi‐arc graphs and the complexity of list homomorphisms
- A Complexity Dichotomy for the Coloring of Sparse Graphs
- Kernelization Lower Bounds by Cross-Composition
- Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials
- Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
- Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
- Space complexity of list H-colouring: a dichotomy
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
This page was built for publication:
