Complexity of \(C_k\)-coloring in hereditary classes of graphs (Q6040658): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.ic.2023.105015
+Normal rank
@@ Property / OpenAlex ID @@
+W4322621584
@@ Property / OpenAlex ID: W4322621584 / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for testing the truth of certain quantified Boolean formulas
+Normal rank
@@ Property / cites work @@
+Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
+Normal rank
@@ Property / cites work @@
+The complexity of surjective homomorphism problems-a survey
+Normal rank
@@ Property / cites work @@
+Three-coloring and list three-coloring of graphs without induced paths on seven vertices
+Normal rank
@@ Property / cites work @@
+A new characterization of \(P_k\)-free graphs
@@ Property / cites work: A new characterization of \(P_k\)-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q5075768
@@ Property / cites work: Q5075768 / rank @@
+Normal rank
@@ Property / cites work @@
+Four-coloring <i>P</i><sub>6</sub>-free graphs
@@ Property / cites work: Four-coloring <i>P</i><sub>6</sub>-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The Monotone Satisfiability Problem with Bounded Variable Appearances
+Normal rank
@@ Property / cites work @@
+The complexity of colouring problems on dense graphs
+Normal rank
@@ Property / cites work @@
+On List Coloring and List Homomorphism of Permutation and Interval Graphs
+Normal rank
@@ Property / cites work @@
+List homomorphisms to reflexive graphs
@@ Property / cites work: List homomorphisms to reflexive graphs / rank @@
+Normal rank
@@ Property / cites work @@
+List homomorphisms and circular arc graphs
@@ Property / cites work: List homomorphisms and circular arc graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Bi‐arc graphs and the complexity of list homomorphisms
+Normal rank
@@ Property / cites work @@
+Extension problems with degree bounds
@@ Property / cites work: Extension problems with degree bounds / rank @@
+Normal rank
@@ Property / cites work @@
+List matrix partitions of chordal graphs
@@ Property / cites work: List matrix partitions of chordal graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Monotone monadic SNP and constraint satisfaction
@@ Property / cites work: Monotone monadic SNP and constraint satisfaction / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of \(H\)-colouring of bounded degree graphs
+Normal rank
@@ Property / cites work @@
+A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
+Normal rank
@@ Property / cites work @@
+Closing complexity gaps for coloring problems on \(H\)-free graphs
+Normal rank
@@ Property / cites work @@
+\(H\)-colouring \(P_t\)-free graphs in subexponential time
+Normal rank
@@ Property / cites work @@
+Polynomial-time algorithm for Maximum Weight Independent Set on <i>P</i><sub>6</sub>-free graphs
+Normal rank
@@ Property / cites work @@
+Q4828516
@@ Property / cites work: Q4828516 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of H-coloring
@@ Property / cites work: On the complexity of H-coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
+Normal rank
@@ Property / cites work @@
+The NP-Completeness of Edge-Coloring
@@ Property / cites work: The NP-Completeness of Edge-Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Q4838453
@@ Property / cites work: Q4838453 / rank @@
+Normal rank
@@ Property / cites work @@
+List-homomorphism problems on graphs and arc consistency
+Normal rank
@@ Property / cites work @@
+Q3558598
@@ Property / cites work: Q3558598 / rank @@
+Normal rank
@@ Property / cites work @@
+Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
+Normal rank
@@ Property / cites work @@
+Q2770587
@@ Property / cites work: Q2770587 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:6040658