scientific article; zbMATH DE number 7525468
From MaRDI portal
Publication:5075768
DOI10.4230/LIPIcs.ESA.2019.31MaRDI QIDQ5075768
Mingxian Zhong, Shenwei Huang, Maria Chudnovsky, Sophie Spirkl, Paweł Rzążewski
Publication date: 11 May 2022
Full work available at URL: https://arxiv.org/abs/2005.01824
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new characterization of \(P_k\)-free graphs
- List-homomorphism problems on graphs and arc consistency
- The complexity of surjective homomorphism problems-a survey
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- List matrix partitions of chordal graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The complexity of colouring problems on dense graphs
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- The complexity of \(H\)-colouring of bounded degree graphs
- Which problems have strongly exponential complexity?
- Triangle-free graphs with no six-vertex induced path
- Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- List homomorphisms and circular arc graphs
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- The NP-Completeness of Edge-Coloring
- Four-coloring P6-free graphs
- Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs
- On List Coloring and List Homomorphism of Permutation and Interval Graphs
- Monotone monadic SNP and constraint satisfaction
- On the complexity of \(k\)-SAT
This page was built for publication:
