Improved complexity results on \(k\)-coloring \(P_t\)-free graphs (Q499486): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1695953772
@@ Property / OpenAlex ID: W1695953772 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.5808
@@ Property / arXiv ID: 1304.5808 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5422499
@@ Property / cites work: Q5422499 / rank @@
+Normal rank
@@ Property / cites work @@
+On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
+Normal rank
@@ Property / cites work @@
+Three complexity results on coloring \(P_k\)-free graphs
+Normal rank
@@ Property / cites work @@
+Updating the complexity status of coloring graphs without a fixed induced linear forest
+Normal rank
@@ Property / cites work @@
+Recognizing Berge graphs
@@ Property / cites work: Recognizing Berge graphs / rank @@
+Normal rank
@@ Property / cites work @@
+‐Coloring             <i>P</i>             <sub>6</sub>             ‐Free Graphs with No Induced 5‐Cycles
+Normal rank
@@ Property / cites work @@
+The strong perfect graph theorem
@@ Property / cites work: The strong perfect graph theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Complement reducible graphs
@@ Property / cites work: Complement reducible graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Colouring vertices of triangle-free graphs without forests
+Normal rank
@@ Property / cites work @@
+The complexity of colouring problems on dense graphs
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Closing Complexity Gaps for Coloring Problems on H-Free Graphs
+Normal rank
@@ Property / cites work @@
+-coloring \(H\)-free graphs when \(H\) is small
@@ Property / cites work: 4-coloring \(H\)-free graphs when \(H\) is small / rank @@
+Normal rank
@@ Property / cites work @@
+Coloring graphs without short cycles and long induced paths
+Normal rank
@@ Property / cites work @@
+Q3216686
@@ Property / cites work: Q3216686 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Coloring Graphs without Paths and Cycles
+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 @@
+Q3558598
@@ Property / cites work: Q3558598 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4448764
@@ Property / cites work: Q4448764 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of 4-coloring graphs without long induced paths
+Normal rank
@@ Property / cites work @@
+NP completeness of finding the chromatic index of regular graphs
+Normal rank
@@ Property / cites work @@
+Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
+Normal rank
@@ Property / cites work @@
+Paw-free graphs
@@ Property / cites work: Paw-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
+Normal rank
@@ Property / cites work @@
+Vertex colouring and forbidden subgraphs -- a survey
+Normal rank
@@ Property / cites work @@
+Depth-First Search and Linear Graph Algorithms
@@ Property / cites work: Depth-First Search and Linear Graph Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Graph colorings with local constraints -- a survey
+Normal rank
@@ Property / cites work @@
+Q2770587
@@ Property / cites work: Q2770587 / rank @@
+Normal rank