Complexity of \(C_k\)-coloring in hereditary classes of graphs
From MaRDI portal
Publication:6040658
DOI10.1016/j.ic.2023.105015OpenAlexW4322621584MaRDI QIDQ6040658
Maria Chudnovsky, Sophie Spirkl, Shenwei Huang, Mingxian Zhong, Paweł Rzążewski
Publication date: 19 May 2023
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2023.105015
Cites Work
- Unnamed Item
- 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
- Extension problems with degree bounds
- The complexity of colouring problems on dense graphs
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- The complexity of \(H\)-colouring of bounded degree graphs
- Which problems have strongly exponential complexity?
- 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
- Bi‐arc graphs and the complexity of list homomorphisms
- The Monotone Satisfiability Problem with Bounded Variable Appearances
- 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
- Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
- On the complexity of \(k\)-SAT
